Lower bounds for treewidth of product graphs

DOI10.1016/J.DAM.2013.08.005zbMath1300.05270OpenAlexW1967494832MaRDI QIDQ741743

Koichi Yamazaki, Kyohei Kozawa, Yota Otachi

Publication date: 12 September 2014

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2013.08.005

zbMATH Keywords

treewidthCartesian productstrong productHadwiger numberbramble

Mathematics Subject Classification ID

Graph operations (line graphs, products, etc.) (05C76)

Related Items (3)

On the treewidth of toroidal grids ⋮ On strict brambles ⋮ On the treewidth of Hanoi graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Clique minors in Cartesian products of graphs
• On the Hadwiger's conjecture for graph products
• Achievable sets, brambles, and sparse treewidth obstructions
• Treewidth lower bounds with brambles
• Treewidth and logical definability of graph products
• Hadwiger's conjecture is true for almost every graph
• A partial k-arboretum of graphs with bounded treewidth
• Graph searching and a min-max theorem for tree-width
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Graph expansion and the unique games conjecture
• Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems
• Finding Large Clique Minors is Hard
• Graph decompositions for cartesian products
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Treewidth of Cartesian Products of Highly Connected Graphs

This page was built for publication: Lower bounds for treewidth of product graphs