𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On bounded treewidth duality of graphs

✍ Scribed by Ne?et?il, Jaroslav; Zhu, Xuding

Publisher
John Wiley and Sons
Year
1996
Tongue
English
Weight
734 KB
Volume
23
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 no such that if G is a graph of girth 2 no then any graph F of treewidth k homomorphic to G is also homomorphic to C2m+l. 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

πŸ“œ SIMILAR VOLUMES

On bounded automorphisms of locally fini
On bounded automorphisms of locally finite transitive graphs
✍ Niemeyer, Peter πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 517 KB

The automorphism-group of an infinite graph acts in a natural way on the set of d-fibers (components of the set of rays with respect to the Hausdorff metric). For connected, locally finite, almost transitive graphs the kernel of this action is proved to be the group of bounded automorphisms. This co

On self duality of pathwidth in polyhedr
On self duality of pathwidth in polyhedral graph embeddings
✍ Fedor V. Fomin; Dimitrios M. Thilikos πŸ“‚ Article πŸ“… 2007 πŸ› John Wiley and Sons 🌐 English βš– 211 KB

## Abstract Let __G__ be a 3‐connected planar graph and __G__^\*^ be its dual. We show that the pathwidth of __G__^\*^ is at most 6 times the pathwidth of __G__. We prove this result by relating the pathwidth of a graph with the cut‐width of its medial graph and we extend it to bounded genus embedd

Optimal Parametric Search on Graphs of B
Optimal Parametric Search on Graphs of Bounded Tree-Width
✍ David FernΓ‘ndez-Baca; Giora Slutzki πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 339 KB

We give linear-time algorithms for a class of parametric search problems on weighted graphs of bounded tree-width. We also discuss the implications of our results to approximate parametric search on planar graphs.

Judicious partitions of bounded-degree g
Judicious partitions of bounded-degree graphs
✍ B. BollobΓ‘s; A. D. Scott πŸ“‚ Article πŸ“… 2004 πŸ› John Wiley and Sons 🌐 English βš– 118 KB πŸ‘ 1 views

## Abstract We prove results on partitioning graphs __G__ with bounded maximum degree. In particular, we provide optimal bounds for bipartitions __V__(__G__) = __V__~1~ βˆͺ __V__~2~ in which we minimize {__e__(__V__~1~), __e__(__V__~2~)}. Β© 2004 Wiley Periodicals, Inc. J Graph Theory 46: 131–143, 200

Efficient and Constructive Algorithms fo
Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
✍ Hans L. Bodlaender; Ton Kloks πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 373 KB

In this paper we give, for all constants k, l, explicit algorithms that, given a graph Ε½ . Gs V,E with a tree-decomposition of G with treewidth at most l, decide Ε½ . whether the treewidth or pathwidth of G is at most k, and, if so, find a Ε½ . tree-decomposition or path-decomposition of G of width at