Strong Cocomparability Graphs and Slash-Free Orderings of Matrices

DOI10.1137/22M153238XarXiv2210.16714MaRDI QIDQ6202755FDOQ6202755

Authors: Pavol Hell, Jing Huang, Jephian Chin-Hung Lin 

Publication date: 27 February 2024

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

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?

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

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

zbMATH Keywords

characterizationrecognitionforbidden submatrixvertex orderingforbidden substructurestrong cocomparability graphstrong comparability graph

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Structural characterization of families of graphs (05C75) Combinatorics of partially ordered sets (06A07)

Cites Work

• Graph Classes: A Survey
• Efficient graph representations
• Domination on Cocomparability Graphs
• Representation of a finite graph by a set of intervals on the real line
• Three Partition Refinement Algorithms
• Transitiv orientierbare Graphen
• A Characterization of Comparability Graphs and of Interval Graphs
• Characterizations of strongly chordal graphs
• Bipartite permutation graphs
• Characterizations of totally balanced matrices
• Domination, independent domination, and duality in strongly chordal graphs
• Totally-Balanced and Greedy Matrices
• Doubly Lexical Orderings of Matrices
• Perfect Elimination and Chordal Bipartite Graphs
• Representation characterizations of chordal bipartite graphs
• The NP-completeness column: an ongoing guide
• Permuting matrices to avoid forbidden submatrices
• List homomorphisms and circular arc graphs
• Approximation of minimum cost homomorphisms
• Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm
• Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms
• Title not available (Why is that?)
• Non-edge orientation and vertex ordering characterizations of some classes of bigraphs
• Ordering without forbidden patterns
• Min-orderable digraphs
• Strong Chordality of Graphs with Possible Loops
• Monotone proper interval digraphs and Min-Max orderings
• Bipartite Analogues of Comparability and Cocomparability Graphs

Cited In (2)

• Gallai-like characterization of strong cocomparability graphs
• Forbidden pattern characterizations of 12-representable graphs defined by pattern-avoiding words

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)