Lower bounds for treewidth of product graphs
From MaRDI portal
Publication:741743
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
Related Items (3)
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