Paper Info
Title
Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms
Abstract
Interval graphs admit linear-time recognition algorithms and have several elegant forbidden structure characterizations. Interval digraphs can also be recognized in polynomial time, and they admit a characterization in terms of incidence matrices. Nevertheless, they do not have a known forbidden structure characterization or low-degree polynomial-time recognition algorithm. We introduce a new class of 'adjusted interval digraphs'. By contrast, for these digraphs we exhibit a natural forbidden structure characterization, in terms of a novel structure which we call an 'invertible pair'. Our characterization also yields a low-degree polynomial-time recognition algorithm of adjusted interval digraphs. It turns out that invertible pairs are also useful for undirected interval graphs, and our result yields a new forbidden structure characterization of interval graphs. In fact, it can be shown to be a natural link proving the equivalence of some known characterizations of interval graphs-the theorems of Lekkerkerker and Boland, and of Fulkerson and Gross. In addition, adjusted interval digraphs naturally arise in the context of list homomorphism problems. If H is a reflexive undirected graph, the list homomorphism problem LHOM(H) is polynomial if H is an interval graph, and NP-complete otherwise. If H is a reflexive digraph, LHOM(H) is polynomial if H is an adjusted interval graph, and we conjecture that it is also NP-complete otherwise. We show that our results imply the conjecture in two important cases.
Year
DOI
Venue
2012
10.1016/j.dam.2011.04.016
Discrete Applied Mathematics
Keywords
Field
DocType
low-degree polynomial-time recognition algorithm,adjusted interval,interval digraphs,interval graph,invertible pair,structure characterization,adjusted interval digraphs,dichotomy,interval digraph,polynomial algorithms,reflexive list homomorphisms,adjusted interval graph,forbidden structure characterizations,list homomorphism problems,undirected interval graph,interval graphs-the theorem,adjusted interval digraph,interval graphs
Discrete mathematics,Combinatorics,Indifference graph,Polynomial,Interval graph,Homomorphism,Invertible matrix,Time complexity,Conjecture,Digraph,Mathematics
Journal
Volume
Issue
ISSN
160
6
Discrete Applied Mathematics
Citations 
PageRank 
References 
12
0.68
16
Authors
4
Name
Order
Citations
PageRank
Tomás Feder11959184.99
Pavol Hell22638288.75
Jing Huang32464186.09
Arash Rafiey433928.08