Treewidth of Products of Graphs with High Treewidth

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.