Interval-like graphs and digraphs

DOI10.4230/LIPICS.MFCS.2018.68MaRDI QIDQ5005172zbMATH OpenFDO

Authors Jing Huang, Arash Rafiey, Pavol Hell, R. M. McConnell

Publication date 4 August 2021

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

zbMATH Keywords

co-TT graphgraph theoryinterval bigraphsinterval graphsmin ordering

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Min-orderable digraphs
• Interval digraphs: An analogue of interval graphs
• scientific article; zbMATH DE number 927077
• Chronological orderings of interval digraphs
• Graphs and digraphs represented by intervals and circular arcs

Cites work

• Approximation of minimum cost homomorphisms
• Characterizations of totally balanced matrices
• Classifying the Complexity of Constraints Using Finite Algebras
• Co-TT graphs and a characterization of split co-TT graphs
• Doubly Lexical Orderings of Matrices
• Efficient graph representations
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3777260 (Why is no real title available?)
• scientific article; zbMATH DE number 15355 (Why is no real title available?)
• Incidence matrices and interval graphs
• Interval digraphs: An analogue of interval graphs
• Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Linear-time recognition of circular-arc graphs
• List homomorphisms and circular arc graphs
• List homomorphisms to reflexive graphs
• On recognition of threshold tolerance graphs and their complements
• Ordering without forbidden patterns
• Permuting matrices to avoid forbidden submatrices
• Polynomial graph-colorings
• Representation characterizations of chordal bipartite graphs
• Representation of a finite graph by a set of intervals on the real line
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The LBFS structure and recognition of interval graphs
• Three Partition Refinement Algorithms
• Threshold tolerance graphs

Cited in

(12)

• A recognition algorithm for adjusted interval digraphs
• scientific article; zbMATH DE number 5954122 (Why is no real title available?)
• Interval Graphs with Containment Restrictions
• scientific article; zbMATH DE number 4053674 (Why is no real title available?)
• Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms
• scientific article; zbMATH DE number 475591 (Why is no real title available?)
• scientific article; zbMATH DE number 1923007 (Why is no real title available?)
• scientific article; zbMATH DE number 861315 (Why is no real title available?)
• scientific article; zbMATH DE number 927077 (Why is no real title available?)
• scientific article; zbMATH DE number 7561584 (Why is no real title available?)
• Min-orderable digraphs
• Towards a dichotomy for the list switch homomorphism problem for signed graphs

This page was built for publication: Interval-like graphs and digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5005172)