2026/07/18 by Raj Kaul
#math.CO #cs.DM
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 tw(G\boxtimes H)≥ (tw(G)+1)had(H)-1 for all graphs G and H, where had(H) is the Hadwiger number of H. We improve this bound to tw(G\boxtimes H)≥ (tw(G)+1)(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.