{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-18","reactions":{}}