Premium
Bi‐arc graphs and the complexity of list homomorphisms
Author(s) -
Feder Tomas,
Hell Pavol,
Huang Jing
Publication year - 2003
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.10073
Subject(s) - combinatorics , mathematics , graph homomorphism , bipartite graph , homomorphism , discrete mathematics , vertex (graph theory) , pathwidth , cograph , graph , line graph , graph power
Given graphs G , H , and lists L ( v ) ⊆ V ( H ), v ε V ( G ), a list homomorphism of G to H with respect to the lists L is a mapping f : V ( G ) → V ( H ) such that u v ε E ( G ) implies f ( u ) f ( v ) ε E ( H ), and f ( v ) ε L ( v ) for all v ε V ( G ). The list homomorphism problem for a fixed graph H asks whether or not an input graph G , together with lists L ( v ) ⊆ V ( H ), v ε V ( G ), admits a list homomorphism with respect to L . In two earlier papers, we classified the complexity of the list homomorphism problem in two important special cases: When H is a reflexive graph (every vertex has a loop), the problem is polynomial time solvable if H is an interval graph, and is NP ‐complete otherwise. When H is an irreflexive graph (no vertex has a loop), the problem is polynomial time solvable if H is bipartite and H is a circular arc graph, and is NP ‐complete otherwise. In this paper, we extend these classifications to arbitrary graphs H (each vertex may or may not have a loop). We introduce a new class of graphs, called bi‐arc graphs, which contains both reflexive interval graphs (and no other reflexive graphs), and bipartite graphs with circular arc complements (and no other irreflexive graphs). We show that the problem is polynomial time solvable when H is a bi‐arc graph, and is NP ‐complete otherwise. In the case when H is a tree (with loops allowed), we give a simpler algorithm based on a structural characterization. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 61–80, 2003