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