Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms
type: Item
instance of: scholarly article
title: Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms
zbMATH Open document ID: 1236.05092
author: Tomás Feder
author: Pavol Hell
author: Arash Rafiey
author: Jing Huang
published in: Discrete Applied Mathematics
publication date: 2012-05-11T00:00:00Z
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 6033756
zbMATH Keywords: interval graphs
zbMATH Keywords: interval digraphs
zbMATH Keywords: adjusted interval digraphs
zbMATH Keywords: forbidden structure characterizations
zbMATH Keywords: polynomial algorithms
zbMATH Keywords: list homomorphism problems
zbMATH Keywords: dichotomy
MaRDI profile type: Publication
full work available at URL: j.dam.2011.04.016
OpenAlex ID: W2052776056
cites work: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
cites work: Complexity of conservative constraint satisfaction problems
cites work: The LBFS Structure and Recognition of Interval Graphs
cites work: Recognition and characterization of chronological interval digraphs
cites work: List homomorphisms to reflexive graphs
cites work: List homomorphisms and circular arc graphs
cites work: Bi‐arc graphs and the complexity of list homomorphisms
cites work: Adjusted interval digraphs
cites work: Digraph matrix partitions and trigraph homomorphisms
cites work: Incidence matrices and interval graphs
cites work: Q3328583
cites work: Polynomial graph-colorings
cites work: Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
cites work: Some remarks on interval graphs
cites work: Q3424890
cites work: Q4828516
cites work: Q5365149
cites work: Q5471351
cites work: Representation of a finite graph by a set of intervals on the real line
cites work: Recognizing interval digraphs and interval bigraphs in polynomial time
cites work: A characterization of interval catch digraphs
cites work: Interval digraphs: An analogue of interval graphs
DOI: 10.1016/J.DAM.2011.04.016
Recommended article: Interval digraphs: An analogue of interval graphs
Recommended article: Q5005172
Recommended article: Q3819103
Recommended article: On the homogeneous representation of interval graphs
Recommended article: Q4329054
Recommended article: On the enumeration of interval graphs
Recommended article: Q4405755
Recommended article: Homogeneously representable interval graphs
Recommended article: On interval representations of graphs
Recommended article: Q3781799
description: scientific article; zbMATH DE number 6033756