Comparability digraphs: an analogue of comparability graphs

DOI10.1016/j.disc.2023.113829zbMath1530.05065arXiv2204.00986MaRDI QIDQ6177431

No author found.

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

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

Cites Work

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