𝔖 Bobbio Scriptorium
✦   LIBER   ✦

CSP duality and trees of bounded pathwidth

✍ Scribed by Catarina Carvalho; Víctor Dalmau; Andrei Krokhin

Book ID
108281649
Publisher
Elsevier Science
Year
2010
Tongue
English
Weight
642 KB
Volume
411
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

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

On bounded treewidth duality of graphs
On bounded treewidth duality of graphs
✍ Ne?et?il, Jaroslav; Zhu, Xuding 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 734 KB

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