Lower bounds for treewidth of product graphs
Two lower bounds for the treewidth of product graphs are presented in terms of the bramble number. The first bound is that the bramble number of the Cartesian product of graphs G1 G 1 and G2 G 2 must be at least the product of the Hadwiger number of G1 G 1 and the PI number of G2 G 2 , where the PI number is a new graph parameter introduced in this paper. The second bound is that the bramble number of the strong product of graphs G1 G 1 and G2 G 2 must be at least the product of the Hadwiger number of G1 G 1 and the bramble number of G2 G 2 . We also demonstrate applications of the lower bounds.
treewidth bramble cartesian product hadwiger number strong product