Strong Cocomparability Graphs and Slash-Free Orderings of Matrices
From MaRDI portal
Publication:6202755
DOI10.1137/22m153238xarXiv2210.16714MaRDI QIDQ6202755
Unnamed Author, Pavol Hell, Jephian C.-H. Lin
Publication date: 27 February 2024
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2210.16714
characterizationrecognitionforbidden submatrixvertex orderingforbidden substructurestrong cocomparability graphstrong comparability graph
Combinatorics of partially ordered sets (06A07) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Structural characterization of families of graphs (05C75)
Cites Work
- Unnamed Item
- Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms
- Domination, independent domination, and duality in strongly chordal graphs
- Characterizations of strongly chordal graphs
- Bipartite permutation graphs
- Efficient graph representations
- Non-edge orientation and vertex ordering characterizations of some classes of bigraphs
- Permuting matrices to avoid forbidden submatrices
- List homomorphisms and circular arc graphs
- Representation characterizations of chordal bipartite graphs
- Approximation of Minimum Cost Homomorphisms
- Ordering without Forbidden Patterns
- Domination on Cocomparability 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
- The NP-completeness column: an ongoing guide
- Doubly Lexical Orderings of Matrices
- Three Partition Refinement Algorithms
- Perfect Elimination and Chordal Bipartite Graphs
- Graph Classes: A Survey
- Monotone Proper Interval Digraphs and Min-Max Orderings
- Bipartite Analogues of Comparability and Cocomparability Graphs
- Min-Orderable Digraphs
- Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm
- Transitiv orientierbare Graphen
- A Characterization of Comparability Graphs and of Interval Graphs
- Strong Chordality of Graphs with Possible Loops
