Treewidth of Products of Graphs with High Treewidth
Discrete Mathematics
Summary
The authors study a property called treewidth, which measures how much a graph looks like a tree. They improve previous results by showing a stronger lower bound on the treewidth of a product of two graphs, solving a question posed by other researchers. They also provide similar results for related measurements like pathwidth and Cartesian products. Finally, they show that certain graph products called expanders contain large subgraphs with good expansion properties.
Authors
Raj Kaul
Abstract
Treewidth is the standard measure for how ``tree-like'' a graph is. This paper studies how the treewidth of a product graph depends on the treewidth of its factors. Kozawa, Otachi, and Yamazaki [2014] and Hickingbotham and Wood [2025] independently showed that $\text{tw}(G\boxtimes H)\geq (\text{tw}(G)+1)\text{had}(H)-1$ for all graphs $G$ and $H$, where $\text{had}(H)$ is the Hadwiger number of $H$. We improve this bound to $\text{tw}(G\boxtimes H)\geq (\text{tw}(G)+1)(\text{tw}(H)+1)-1$, thereby solving an open problem of Hickingbotham and Wood. We also prove analogous product inequalities for pathwidth, Cartesian products, and strict bramble number, which is a parameter that is tied to treewidth. As an application of our results, we show that products of expanders have large subgraphs that are expanders.