๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Lower bounds for treewidth of product graphs

โœ Scribed by Kozawa, Kyohei; Otachi, Yota; Yamazaki, Koichi

Book ID
122491918
Publisher
Elsevier Science
Year
2014
Tongue
English
Weight
416 KB
Volume
162
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

A spectral lower bound for the treewidth
A spectral lower bound for the treewidth of a graph and its consequences
โœ L.Sunil Chandran; C.R. Subramanian ๐Ÿ“‚ Article ๐Ÿ“… 2003 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 95 KB

We give a lower bound for the treewidth of a graph in terms of the second smallest eigenvalue of its Laplacian matrix. We use this lower bound to show that the treewidth of a d-dimensional hypercube is at least 3 We generalize this result to Hamming graphs. We also observe that every graph G on n v

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