Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms

DOI10.1016/j.dam.2011.04.016zbMath1236.05092OpenAlexW2052776056MaRDI QIDQ415269

Pavol Hell, Tomás Feder, Arash Rafiey, Jing Huang

Publication date: 11 May 2012

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2011.04.016

zbMATH Keywords

polynomial algorithmsinterval graphsdichotomyadjusted interval digraphsforbidden structure characterizationsinterval digraphslist homomorphism problems

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items

Unnamed Item ⋮ 2-nested matrices: towards understanding the structure of circle graphs ⋮ Digraph matrix partitions and trigraph homomorphisms ⋮ A recognition algorithm for adjusted interval digraphs ⋮ Chordal digraphs ⋮ Recognition and characterization of chronological interval digraphs ⋮ Recognizing interval bigraphs by forbidden patterns ⋮ On the kernel and related problems in interval digraphs ⋮ Min orderings and list homomorphism dichotomies for signed and unsigned graphs ⋮ Minimum Cost Homomorphism Dichotomy for Oriented Cycles ⋮ Unnamed Item ⋮ Classes of intersection digraphs with good algorithmic properties ⋮ Strong Cocomparability Graphs and Slash-Free Orderings of Matrices ⋮ Min-Orderable Digraphs ⋮ Bounded Tree-Width and CSP-Related Problems ⋮ Strict chordal and strict split digraphs ⋮ The complexity of the minimum cost homomorphism problem for semicomplete digraphs with possible loops ⋮ Minimum Cost Homomorphisms to Reflexive Digraphs ⋮ Strong Chordality of Graphs with Possible Loops

Cites Work

• Recognition and characterization of chronological interval digraphs
• Digraph matrix partitions and trigraph homomorphisms
• Some remarks on interval graphs
• A characterization of interval catch digraphs
• List homomorphisms to reflexive graphs
• Polynomial graph-colorings
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Recognizing interval digraphs and interval bigraphs in polynomial time
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• List homomorphisms and circular arc graphs
• Incidence matrices and interval graphs
• Adjusted Interval Digraphs
• Complexity of conservative constraint satisfaction problems
• The LBFS Structure and Recognition of Interval Graphs
• Representation of a finite graph by a set of intervals on the real line
• Interval digraphs: An analogue of interval graphs
• Bi‐arc graphs and the complexity of list homomorphisms
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item