Interval k-graphs and orders

DOI10.1007/S11083-017-9445-0MaRDI QIDQ1789058zbMATH OpenOpenAlexFDO

Authors David E. Brown, Breeann M. Flesch, Larry J. Langley

Publication date 9 October 2018

Published in Order (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1602.08669

zbMATH Keywords

forbidden subgraph characterizationinterval \(k\)-graphsinterval graphsinterval orders

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Combinatorics of partially ordered sets (06A07)

Abstract: An interval $k$-graph is the intersection graph of a family $mathcalI$ 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.

Recommendations

• scientific article; zbMATH DE number 1933220
• Probe interval orders
• Interval graphs and interval orders
• A simple proof characterizing interval orders with interval lengths between 1 and \(k\)
• A characterization of uniquely representable interval graphs

Cites work

• A characterization of 2-tree proper interval 3-graphs
• A characterization of cycle-free unit probe interval graphs
• A decomposition theorem for partially ordered sets
• Asteroidal Triple-Free Graphs
• Bipartite permutation graphs
• Bipartite probe interval graphs, circular arc graphs, and interval point bigraphs
• Characterizations for unit interval bigraphs
• Circular-arc graphs with clique cover number two
• Comparability graphs and intersection graphs
• scientific article; zbMATH DE number 1439437 (Why is no real title available?)
• scientific article; zbMATH DE number 3318595 (Why is no real title available?)
• Incidence matrices and interval graphs
• Indifference Digraphs: A Generalization of Indifference Graphs and Semiorders
• Interval bigraphs and circular arc graphs
• Interval digraphs: An analogue of interval graphs
• On probe interval graphs
• Probe interval orders
• Topics in Intersection Graph Theory
• Transitiv orientierbare Graphen
• Weakly triangulated graphs

Cited in

(11)

• Interval graphs and interval orders
• Distances in cocomparability graphs and their powers
• The order-interval hypergraph of a finite poset and the König property
• Parikh word representability of bipartite permutation graphs
• Sortable simplicial complexes and \(t\)-independence ideals of proper interval graphs
• Ordered graphs and large bi-cliques in intersection graphs of curves
• scientific article; zbMATH DE number 3877239 (Why is no real title available?)
• scientific article; zbMATH DE number 1933220 (Why is no real title available?)
• Asteroidal-triple-free interval \(k\)-graphs
• L(p,q)-labeling of graphs with interval representations
• Exchangeable interval hypergraphs and limits of ordered discrete structures

This page was built for publication: Interval \(k\)-graphs and orders

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1789058)