Bipartite Analogues of Comparability and Cocomparability Graphs
From MaRDI portal
Publication:5128518
Abstract: We propose bipartite analogues of comparability and cocomparability graphs. Surprizingly, the two classes coincide. We call these bipartite graphs cocomparability bigraphs. We characterize cocomparability bigraphs in terms of vertex orderings, forbidden substructures, and orientations of their complements. In particular, we prove that cocomparability bigraphs are precisely those bipartite graphs that do not have edge-asteroids; this is analogous to Gallai's structural characterization of cocomparability graphs by the absence of (vertex-) asteroids. Our characterizations imply a robust polynomial-time recognition algorithm for the class of cocomparability bigraphs. Finally, we also discuss a natural relation of cocomparability bigraphs to interval containment bigraphs, resembling a well-known relation of cocomparability graphs to interval graphs.
Recommendations
- scientific article; zbMATH DE number 4061296
- Cocomplete bipartite graphs
- scientific article; zbMATH DE number 4193736
- scientific article; zbMATH DE number 4043898
- scientific article; zbMATH DE number 966717
- Comparability graphs among cover-incomparability graphs
- Biclique comparability digraphs of bipartite graphs and minimum ranks of partial matrices
- Cohen-Macaulay bipartite graphs
- On Comparability and Permutation Graphs
- A class of `matching-equivalent' bipartite graphs
Cites work
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 3815694 (Why is no real title available?)
- scientific article; zbMATH DE number 15355 (Why is no real title available?)
- scientific article; zbMATH DE number 1990673 (Why is no real title available?)
- A Characterization of Comparability Graphs and of Interval Graphs
- A general approach to avoiding two by two submatrices
- Asteroidal Triple-Free Graphs
- Bipartite permutation graphs
- Characterizations of totally balanced matrices
- Doubly Lexical Orderings of Matrices
- Graph Classes: A Survey
- Interval bigraphs and circular arc graphs
- Interval digraphs: An analogue of interval graphs
- Linear-time recognition of circular-arc graphs
- List homomorphisms and circular arc graphs
- Modular decomposition and transitive orientation
- Non-edge orientation and vertex ordering characterizations of some classes of bigraphs
- On opposition graphs, coalition graphs, and bipartite permutation graphs
- On orthogonal ray graphs
- Perfect Elimination and Chordal Bipartite Graphs
- Permutation bigraphs and interval containments
- Permuting matrices to avoid forbidden submatrices
- Recognizing interval digraphs and interval bigraphs in polynomial time
- Representation characterizations of chordal bipartite graphs
- Representation of a finite graph by a set of intervals on the real line
- Representing digraphs using intervals or circular arcs
- Three Partition Refinement Algorithms
- Totally-Balanced and Greedy Matrices
- Transitiv orientierbare Graphen
- Which claw-free graphs are perfectly orderable?
Cited in
(5)- Characterization and a 2D Visualization of B$$_{0}$$-VPG Cocomparability Graphs
- Strong Cocomparability Graphs and Slash-Free Orderings of Matrices
- Comparability digraphs: an analogue of comparability graphs
- Gallai-like characterization of strong cocomparability graphs
- Non-edge orientation and vertex ordering characterizations of some classes of bigraphs
This page was built for publication: Bipartite Analogues of Comparability and Cocomparability Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5128518)
