Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userProper and Unit Trapezoid Orders and Graphs
125
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We show that the class of trapezoid orders in which no trapezoid strictly contains any other trapezoid strictly contains the class of trapezoid orders in which every trapezoid can be drawn with unit area. This is different from the case of interval orders, where the class of proper interval orders is exactly the same as the class of unit interval orders.
rate research
Read More
An interval $k$-graph is the intersection graph of a family $mathcal{I}$ of intervals of the real line partitioned into at most $k$ classes with vertices adjacent if and only if their corresponding intervals intersect and belong to different classes. In this paper we discuss the interval $k$-graphs that are the incomparability graphs of orders; i.e., cocomparability interval $k$-graphs or interval $k$-orders. Interval $2$-orders have been characterized in many ways, but we show that analogous characterizations do not carry over to interval $k$-orders, for $k > 2$. We describe the structure of interval $k$-orders, for any $k$, characterize the interval $3$-orders (cocomparability interval $3$-graphs) via one forbidden suborder (subgraph), and state a conjecture for interval $k$-orders (any $k$) that would characterize them via two forbidden suborders.
A short proof is given that the graphs with proper interval representations are the same as the graphs with unit interval representations.
In this paper we extend the work of Rautenbach and Szwarcfiter by giving a structural characterization of graphs that can be represented by the intersection of unit intervals that may or may not contain their endpoints. A characterization was proved independently by Joos, however our approach provides an algorithm that produces such a representation, as well as a forbidden graph characterization.
Interval graphs were used in the study of genomics by the famous molecular biologist Benzer. Later on probe interval graphs were introduced by Zhang as a generalization of interval graphs for the study of cosmid contig mapping of DNA. A tagged probe interval graph (briefly, TPIG) is motivated by similar applications to genomics, where the set of vertices is partitioned into two sets, namely, probes and nonprobes and there is an interval on the real line corresponding to each vertex. The graph has an edge between two probe vertices if their corresponding intervals intersect, has an edge between a probe vertex and a nonprobe vertex if the interval corresponding to a nonprobe vertex contains at least one end point of the interval corresponding to a probe vertex and the set of non-probe vertices is an independent set. This class of graphs have been defined nearly two decades ago, but till today there is no known recognition algorithm for it. In this paper, we consider a natural subclass of TPIG, namely, the class of proper tagged probe interval graphs (in short PTPIG). We present characterization and a linear time recognition algorithm for PTPIG. To obtain this characterization theorem we introduce a new concept called canonical sequence for proper interval graphs, which, we belief, has an independent interest in the study of proper interval graphs. Also to obtain the recognition algorithm for PTPIG, we introduce and solve a variation of consecutive $1$s problem, namely, oriented consecutive $1$s problem and some variations of PQ-tree algorithm. We also discuss the interrelations between the classes of PTPIG and TPIG with probe interval graphs and probe proper interval graphs.
A tree $T$ in an edge-colored graph is a emph{proper tree} if any two adjacent edges of $T$ are colored with different colors. Let $G$ be a graph of order $n$ and $k$ be a fixed integer with $2leq kleq n$. For a vertex set $Ssubseteq V(G)$, a tree containing the vertices of $S$ in $G$ is called an emph{$S$-tree}. An edge-coloring of $G$ is called a emph{$k$-proper coloring} if for every set $S$ of $k$ vertices in $G$, there exists a proper $S$-tree in $G$. The emph{$k$-proper index} of a nontrivial connected graph $G$, denoted by $px_k(G)$, is the smallest number of colors needed in a $k$-proper coloring of $G$. In this paper, some simple observations about $px_k(G)$ for a nontrivial connected graph $G$ are stated. Meanwhile, the $k$-proper indices of some special graphs are determined, and for every pair of positive integers $a$, $b$ with $2leq aleq b$, a connected graph $G$ with $px_k(G)=a$ and $rx_k(G)=b$ is constructed for each integer $k$ with $3leq kleq n$. Also, the graphs with $k$-proper index $n-1$ and $n-2$ are respectively characterized.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
