Brambles, Prisms and Grids
Étienne Birmelé, J. A. Bondy, Bruce A. Reed · Birkhäuser Basel eBooks · 2006
The Cartesian product C κ × K 2 of a circuit of length κ with K 2 is called a κ-prism. It is well known that graphs not having the κ-prism as a minor have their tree-width bounded by an exponential function of κ. Using brambles and their well-studied relation to tree-width, we show that they have in fact tree-width O(κ 2). As a consequence, we obtain new bounds on the tree-width of graphs having no small grid as a minor.