Min-Orderable Digraphs
From MaRDI portal
Publication:5130576
DOI10.1137/19M1241763zbMath1450.05036OpenAlexW3046665623MaRDI QIDQ5130576
Arash Rafiey, Jing Huang, Pavol Hell, Ross M. McConnell
Publication date: 28 October 2020
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/19m1241763
Structural characterization of families of graphs (05C75) Directed graphs (digraphs), tournaments (05C20) Graph representations (geometric and intersection representations, etc.) (05C62) Perfect graphs (05C17)
Related Items
A recognition algorithm for adjusted interval digraphs ⋮ Comparability digraphs: an analogue of comparability graphs ⋮ Strong Cocomparability Graphs and Slash-Free Orderings of Matrices ⋮ Strong Chordality of Graphs with Possible Loops
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On recognition of threshold tolerance graphs and their complements
- Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms
- Characterizations of strongly chordal graphs
- List homomorphisms to reflexive graphs
- Polynomial graph-colorings
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Efficient graph representations
- Linear-time recognition of circular-arc graphs
- Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
- Permuting matrices to avoid forbidden submatrices
- List homomorphisms and circular arc graphs
- Incidence matrices and interval graphs
- Co-TT graphs and a characterization of split co-TT graphs
- Representation characterizations of chordal bipartite graphs
- Approximation of Minimum Cost Homomorphisms
- Ordering without Forbidden Patterns
- The LBFS Structure and Recognition of Interval Graphs
- Representation of a finite graph by a set of intervals on the real line
- Characterizations of totally balanced matrices
- Doubly Lexical Orderings of Matrices
- Threshold tolerance graphs
- Interval digraphs: An analogue of interval graphs
- Containment Graphs, Posets, and Related Classes of Graphs
- Bi‐arc graphs and the complexity of list homomorphisms
- Interval bigraphs and circular arc graphs
- Monotone Proper Interval Digraphs and Min-Max Orderings
- Classifying the Complexity of Constraints Using Finite Algebras
