Comparability digraphs: an analogue of comparability graphs

DOI10.1016/J.DISC.2023.113829MaRDI QIDQ6177431zbMATH OpenFDO

Authors

Publication date 17 January 2024

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

characterizationrecognition algorithmknotting graphcomparability digraphtriangle lemmaimplication class

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Structural characterization of families of graphs (05C75)

Abstract: Comparability graphs are a popular class of graphs. We introduce as the digraph analogue of comparability graphs the class of comparability digraphs. We show that many concepts such as implication classes and the knotting graph for a comparability graph can be naturally extended to a comparability digraph. We give a characterization of comparability digraphs in terms of their knotting graphs. Semicomplete comparability digraphs are a prototype of comparability digraphs. One instrumental technique for analyzing the structure of comparability graphs is the Triangle Lemma for graphs. We generalize the Triangle Lemma to semicomplete digraphs. Using the Triangle Lemma for semicomplete digraphs we prove that if an implication class of a semicomplete digraph contains no circuit of length 2 then it contains no circuit at all. We also use it to device an $mathcalO(n^3)$ time recognition algorithm for semicomplete comparability digraphs where $n$ is the number of vertices of the input digraph. The correctness of the algorithm implies a characterization for semicomplete comparability digraphs, akin to that for comparability graphs.

Recommendations

• scientific article; zbMATH DE number 1554932
• Cycle-free partial orders and chordal comparability graphs
• scientific article; zbMATH DE number 3908482
• On Comparability and Permutation Graphs
• Lexicographic orientation and representation algorithms for comparability graphs, proper circular arc graphs, and proper interval graphs

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• A complete axiomatisation for the inclusion of series-parallel partial orders
• A general approach to avoiding two by two submatrices
• Arboricity, \(h\)-index, and dynamic algorithms
• Bipartite Analogues of Comparability and Cocomparability Graphs
• Characterizations of totally balanced matrices
• Circular‐arc digraphs: A characterization
• Interval digraphs: An analogue of interval graphs
• Lexicographic orientation and representation algorithms for comparability graphs, proper circular arc graphs, and proper interval graphs
• Min-orderable digraphs
• Modular decomposition and transitive orientation
• Oriented threshold graphs
• Permuting matrices to avoid forbidden submatrices
• Split digraphs
• The complexity of comparability graph recognition and coloring
• Totally-Balanced and Greedy Matrices
• Toward Characterization of Perfect Elimination Digraphs
• Transitiv orientierbare Graphen

Cited in

(1)

• Forbidden pattern characterizations of 12-representable graphs defined by pattern-avoiding words

This page was built for publication: Comparability digraphs: an analogue of comparability graphs

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