Bipartite Analogues of Comparability and Cocomparability Graphs

DOI10.1137/19M1263789zbMath1450.05089arXiv1902.00213MaRDI QIDQ5128518

Jephian C.-H. Lin, Jing Huang, Pavol Hell, Ross M. McConnell

Publication date: 27 October 2020

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

characterizationpolynomial time algorithmrecognitionorientationasteroidinterval bigraphvertex orderinginvertible pairedge-asteroidchordal bigraphinterval containment bigraphcocomparability bigraphtwo-directional orthogonal-ray graph

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (05C99)

Related Items (2)

Comparability digraphs: an analogue of comparability graphs ⋮ Strong Cocomparability Graphs and Slash-Free Orderings of Matrices

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Permutation bigraphs and interval containments
• On orthogonal ray graphs
• Which claw-free graphs are perfectly orderable?
• Bipartite permutation graphs
• Modular decomposition and transitive orientation
• A general approach to avoiding two by two submatrices
• Recognizing interval digraphs and interval bigraphs in polynomial time
• Linear-time recognition of circular-arc graphs
• Non-edge orientation and vertex ordering characterizations of some classes of bigraphs
• Permuting matrices to avoid forbidden submatrices
• Representing digraphs using intervals or circular arcs
• List homomorphisms and circular arc graphs
• On opposition graphs, coalition graphs, and bipartite permutation graphs
• Representation characterizations of chordal bipartite graphs
• 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
• Three Partition Refinement Algorithms
• Interval digraphs: An analogue of interval graphs
• Perfect Elimination and Chordal Bipartite Graphs
• Graph Classes: A Survey
• Asteroidal Triple-Free Graphs
• Interval bigraphs and circular arc graphs
• Transitiv orientierbare Graphen
• A Characterization of Comparability Graphs and of Interval Graphs

This page was built for publication: Bipartite Analogues of Comparability and Cocomparability Graphs