Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms
From MaRDI portal
Publication:415269
DOI10.1016/J.DAM.2011.04.016zbMATH Open1236.05092OpenAlexW2052776056MaRDI QIDQ415269FDOQ415269
Authors: Tomás Feder, Pavol Hell, 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
Recommendations
- Interval digraphs: An analogue of interval graphs
- Interval-like graphs and digraphs
- scientific article; zbMATH DE number 4091559
- On the homogeneous representation of interval graphs
- scientific article; zbMATH DE number 1735663
- On the enumeration of interval graphs
- scientific article; zbMATH DE number 1933220
- Homogeneously representable interval graphs
- On interval representations of graphs
- scientific article; zbMATH DE number 4043897
interval graphsdichotomypolynomial algorithmsadjusted interval digraphsforbidden structure characterizationsinterval digraphslist homomorphism problems
Cites Work
- A characterization of interval catch digraphs
- Interval digraphs: An analogue of interval graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Incidence matrices and interval graphs
- Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
- Complexity of conservative constraint satisfaction problems
- Representation of a finite graph by a set of intervals on the real line
- Recognition and characterization of chronological interval digraphs
- Digraph matrix partitions and trigraph homomorphisms
- List homomorphisms and circular arc graphs
- The LBFS structure and recognition of interval graphs
- List homomorphisms to reflexive graphs
- Bi‐arc graphs and the complexity of list homomorphisms
- Polynomial graph-colorings
- Title not available (Why is that?)
- Recognizing interval digraphs and interval bigraphs in polynomial time
- Adjusted interval digraphs
- Some remarks on interval graphs
- From graph coloring to constraint satisfaction: there and back again
- Title not available (Why is that?)
Cited In (23)
- The complexity of the minimum cost homomorphism problem for semicomplete digraphs with possible loops
- Title not available (Why is that?)
- Criterion for equational Noetherianity and complexity of the solvability problem for systems of equations over partially ordered sets
- Minimum Cost Homomorphism Dichotomy for Oriented Cycles
- Min orderings and list homomorphism dichotomies for graphs and signed graphs
- Chordal digraphs
- Recognizing interval bigraphs by forbidden patterns
- Forbidden pattern characterizations of 12-representable graphs defined by pattern-avoiding words
- On the kernel and related problems in interval digraphs
- Minimum Cost Homomorphisms to Reflexive Digraphs
- 2-nested matrices: towards understanding the structure of circle graphs
- Recognition and characterization of chronological interval digraphs
- A recognition algorithm for adjusted interval digraphs
- Title not available (Why is that?)
- Classes of intersection digraphs with good algorithmic properties
- Strong Cocomparability Graphs and Slash-Free Orderings of Matrices
- Bounded Tree-Width and CSP-Related Problems
- Digraph matrix partitions and trigraph homomorphisms
- Min orderings and list homomorphism dichotomies for signed and unsigned graphs
- Strict chordal and strict split digraphs
- Min-Orderable Digraphs
- Bi-arc digraphs: recognition algorithm and applications
- Strong Chordality of Graphs with Possible Loops
This page was built for publication: Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q415269)
