Interval k-graphs and orders

DOI10.1007/S11083-017-9445-0zbMATH Open1406.06002arXiv1602.08669OpenAlexW2963137092MaRDI QIDQ1789058FDOQ1789058

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

Publication date: 9 October 2018

Published in: Order (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

interval graphsinterval ordersforbidden subgraph characterizationinterval \(k\)-graphs

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (9)

• Ordered graphs and large bi-cliques in intersection graphs of curves
• Title not available (Why is that?)
• The order-interval hypergraph of a finite poset and the König property
• Parikh word representability of bipartite permutation graphs
• Interval graphs and interval orders
• Title not available (Why is that?)
• Asteroidal-triple-free interval \(k\)-graphs
• Exchangeable interval hypergraphs and limits of ordered discrete structures
• Sortable simplicial complexes and \(t\)-independence ideals of proper interval graphs

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)