January 28, 2008
Graph minors and products
David Wood
Universitat Politecnica de Catalunya
A "clique minor" in a graph can be thought of as a set of connected subgraphs that are pairwise disjoint and pairwise adjacent. This talk is about clique minors in the Cartesian product of graphs.

The main result is a rough structural characterisation theorem for Cartesian products with bounded clique minors (that is less rough than the general structure theorem of Robertson and Seymour). For example, it implies that if the product of two sufficiently large graphs has bounded clique minors then it is: (1) a planar grid (product of two paths) plus a vortex of bounded width in the outerface, (2) a cylindrical grid (product of a path and a cycle) plus a vortex of bounded width in each of the two `big' faces, or (3) a toroidal grid (product of two cycles).

We also develop connections with pseudoachromatic colourings and connected dominating sets that imply near-tight bounds on maximum cardinality of a clique minor in grid graphs (products of paths) and Hamming graphs (products of cliques). Finally, Hadwiger's conjecture for Cartesian products will be discussed.

Only basic graph theory will be assumed.