Treewidth of Cartesian Products of Highly Connected Graphs

Abstract

The following theorem is proved: For all $k$-connected graphs $G$ and $H$ each with at least $n$ vertices, the treewidth of the cartesian product of $G$ and $H$ is at least $k(n-2k+2)-1$. For $n\gg k$ this lower bound is asymptotically tight for particular graphs $G$ and $H$. This theorem generalises a well known result about the treewidth of planar grid graphs.

References in corpus (1)

• Clique Minors in Cartesian Products of Graphs

Cited by in corpus (2)

• Planar graphs have bounded queue-number
• Treewidth of the $q$-Kneser graphs