Strong Cocomparability Graphs and Slash-Free Orderings of Matrices
From MaRDI portal
Publication:6202755
Abstract: We introduce the class of strong cocomparability graphs, as the class of reflexive graphs whose adjacency matrix can be rearranged by a simultaneous row and column permutation to avoid the submatrix with rows 01, 10, which we call Slash. We provide an ordering characterization, a forbidden structure characterization, and a polynomial-time recognition algorithm, for the class. These results complete the picture in which in addition to, or instead of, the Slash matrix one forbids the Gamma matrix (which has rows 11, 10). It is well known that in these two cases one obtains the class of interval graphs, and the class of strongly chordal graphs, respectively. By complementation, we obtain the class of strong comparability graphs, whose adjacency matrix can be rearranged by a simultaneous row and column permutation to avoid the two-by-two identity submatrix. Thus our results give characterizations and algorithms for this class of irreflexive graphs as well. In other words, our results may be interpreted as solving the following problem: given a symmetric 0,1-matrix with 0-diagonal, can the rows and columns of be simultaneously permuted to avoid the two-by-two identity submatrix?
Recommendations
- Gallai-like characterization of strong cocomparability graphs
- Strongly orderable graphs. A common generalization of strongly chordal and chordal bipartite graphs
- scientific article; zbMATH DE number 2044941
- On the power of graph searching for cocomparability graphs
- scientific article; zbMATH DE number 1302027
Cites work
- scientific article; zbMATH DE number 15355 (Why is no real title available?)
- A Characterization of Comparability Graphs and of Interval Graphs
- Approximation of minimum cost homomorphisms
- Bipartite Analogues of Comparability and Cocomparability Graphs
- Bipartite permutation graphs
- Characterizations of strongly chordal graphs
- Characterizations of totally balanced matrices
- Domination on Cocomparability Graphs
- Domination, independent domination, and duality in strongly chordal graphs
- Doubly Lexical Orderings of Matrices
- Efficient graph representations
- Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm
- Graph Classes: A Survey
- Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms
- List homomorphisms and circular arc graphs
- Min-orderable digraphs
- Monotone proper interval digraphs and Min-Max orderings
- Non-edge orientation and vertex ordering characterizations of some classes of bigraphs
- Ordering without forbidden patterns
- Perfect Elimination and Chordal Bipartite Graphs
- Permuting matrices to avoid forbidden submatrices
- Representation characterizations of chordal bipartite graphs
- Representation of a finite graph by a set of intervals on the real line
- Strong Chordality of Graphs with Possible Loops
- The NP-completeness column: an ongoing guide
- Three Partition Refinement Algorithms
- Totally-Balanced and Greedy Matrices
- Transitiv orientierbare Graphen
Cited in
(2)
This page was built for publication: Strong Cocomparability Graphs and Slash-Free Orderings of Matrices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6202755)
