2016/02/28 by David E. Brown, Brown, David E., Breeann M. Flesch +3
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1602.08669
arxiv created 2016/02/28 · arxiv updated 2016/03/01
An interval k-graph is the intersection graph of a family 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.