Name
Abstract | ||
|---|---|---|
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. In this paper we study the cocomparability interval k-graphs; that is, the interval k-graphs whose complements have a transitive orientation and are therefore the incomparability graphs of strict partial orders. For brevity we call these orders interval k-orders. We characterize the kind of interval representations a cocomparability interval k-graph must have, and identify the structure that guarantees an order is an interval k-order. The case k = 2 is peculiar: cocomparability interval 2-graphs (equivalently proper- or unit-interval bigraphs, bipartite permutation graphs, and complements of proper circular-arc graphs to name a few) have been characterized in many ways, but we show that analogous characterizations do not hold if k > 2. We characterize the cocomparability interval 3-graphs via one forbidden subgraph and hence interval 3-orders via one forbidden suborder. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1007/s11083-017-9445-0 | ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS |
Keywords | Field | DocType |
Interval graphs,Interval orders,Interval k-graphs,Forbidden subgraph characterization | Discrete mathematics,Combinatorics,Interval order,Interval graph,Vertex (geometry),Real line,Intersection graph,If and only if,Conjecture,Mathematics,The Intersect | Journal |
Volume | Issue | ISSN |
35.0 | 3 | 0167-8094 |
Citations | PageRank | References |
0 | 0.34 | 6 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| David E. Brown | 1 | 15 | 2.74 |
| Breeann Flesch | 2 | 0 | 0.68 |
| Larry J. Langley | 3 | 14 | 5.19 |