Interval \(k\)-graphs and orders (Q1789058)

An interval \(k\)-graph is the intersection graph of a family of intervals of the real line partitioned into \(k\) classes with vertices adjacent if and only if their corresponding intervals intersect and belong to different classes. The authors study the cocomparability interval \(k\)-graphs, that is, those interval \(k\)-graphs whose complements have a transitive orientation (and consequently are the incomparability graphs of strict partial orders). Such orders are called interval \(k\)-orders in the following. In this paper, they characterize the kind of interval representations a cocomparability interval \(k\)-graph has. Furthermore, they identify the structure that guarantees that an order is an interval \(k\)-order. The case \(k=2\) turns out to be somewhat peculiar: Cocomparability interval \(2\)-graphs appear in the mathematical literature under many different names. It is argued however that analogous characterizations do no longer hold if \(k>2\). Finally, the cocomparability interval \(3\)-graphs are characterized with the help of one forbidden subgraph, and similarly interval \(3\)-orders via one forbidden suborder.