Treewidth of Cartesian Products of Highly Connected Graphs

الأصل · EN

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≫ 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.