Id: arxiv/2607.16778 Url: https://arxiv.org/abs/2607.16778 Tags: math.CO, cs.DM Score: 0 Title: Treewidth of Products of Graphs with High Treewidth Domain: math.CO Source: arxiv Authors: Raj Kaul Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-07-18 Page: https://delphi.science/r/arxiv/2607.16778 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…