Gallai-like characterization of strong cocomparability graphs

DOI10.1002/jgt.23113zbMATH Open1546.05085MaRDI QIDQ6595514

Unnamed Author

Publication date: 30 August 2024

Published in: Journal of Graph Theory (Search for Journal in Brave)

zbMATH Keywords

comparability graphcocomparability graphasteroidedge-asteroidpolynomial time recognition algorithmstrong cocomparability graphGallai-like characterizationweak edge-asteroid

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Characterizations of strongly chordal graphs
• Comparability graphs and intersection graphs
• The complexity of comparability graph recognition and coloring
• List homomorphisms and circular arc graphs
• Representation characterizations of chordal bipartite graphs
• Vertex Ordering Characterizations of Graphs of Bounded Asteroidal Number
• Representation of a finite graph by a set of intervals on the real line
• Characterizations of totally balanced matrices
• Totally-Balanced and Greedy Matrices
• Doubly Lexical Orderings of Matrices
• Perfect Elimination and Chordal Bipartite Graphs
• Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs
• Asteroidal Triple-Free Graphs
• Lexicographic orientation and representation algorithms for comparability graphs, proper circular arc graphs, and proper interval graphs
• Bipartite Analogues of Comparability and Cocomparability Graphs
• Transitiv orientierbare Graphen
• A Characterization of Comparability Graphs and of Interval Graphs
• The diameter of AT‐free graphs
• Strong Cocomparability Graphs and Slash-Free Orderings of Matrices

This page was built for publication: Gallai-like characterization of strong cocomparability graphs