Premium
On bounded treewidth duality of graphs
Author(s) -
Nešetřil Jaroslav,
Zhu Xuding
Publication year - 1996
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/(sici)1097-0118(199610)23:2<151::aid-jgt6>3.0.co;2-s
Subject(s) - treewidth , combinatorics , mathematics , partial k tree , 1 planar graph , discrete mathematics , tree depth , clique sum , graph coloring , bounded function , pathwidth , graph , chordal graph , line graph , mathematical analysis
For a graph H, the H ‐coloring problem is to decide whether or not an instance graph G is homomorphic to H . The H ‐coloring problem is said to have bounded treewidth duality if there is an integer k such that for any graph G which is not homomorphic to H, there is a graph F of treewidth k which is homomorphic to G but not homomorphic to H . It is known that if the H ‐coloring problem has bounded treewidth duality then it is polynomial time decidable. We shall prove in this paper that for any integers m, k, there is an integer n 0 such that if G is a graph of girth ≥ n 0 then any graph F of treewidth k homomorphic to G is also homomorphic to C 2 m +1 . It follows from this result that for non‐bipartite graphs H, the H ‐coloring problems do not have bounded treewidth duality. We also present some classes of directed graphs H for which the H ‐coloring problems do not have bounded treewidth duality. In particular, there are oriented cycles H for which the H ‐coloring problems do not have bounded treewidth duality. This answers a question of Hell and Zhu ( Siam J. Discrete Math., 8 (1995), 208–222). © 1996 John Wiley & Sons, Inc.