Hadwiger number and the cartesian product operation on graphs

Abstract

The Hadwiger number ?(G) of a graph G is defined as the largest integer n for which the complete graph on n nodes K? is a minor of G. Hadwiger conjectured that for any graph G, ?(G) ? ?(G), where ?(G) is the chromatic number of G. In this thesis, we investigate the Hadwiger number with respect to the Cartesian product operation on graphs. As the main result of this thesis, we show that for any two graphs G? and G? with ?(G?) = h and ?(G?) = l, ?(G? ? G?) ? ?(h ? 2) · l. (Since G? ? G? is isomorphic to G? ? G?, we can assume without loss of generality that h ? l). This lower bound is the best possible (up to a small constant factor), since if G? = K? and G? = K?, ?(G? ? G?) ? 2h?l. We also show that ?(G? ? G?) does not have any upper bound which depends only on ?(G?) and ?(G?), by demonstrating graphs G? and G? such that ?(G?) and ?(G?) are bounded whereas ?(G? ? G?) grows with the number of nodes. (The problem of studying the Hadwiger number with respect to the Cartesian product operation was posed by Z. Miller in 1978.) As consequences of our main result, we show the following:

Let G be a connected graph. Let the (unique) prime factorization of G be given by G? ? G? ? … ? G?. Then G satisfies Hadwiger's conjecture if k ? 2 log log ?(G) + c, where c is a constant. This improves the 2 log ?(G) + 3 bound given in [2].

Let G? and G? be two graphs such that ?(G?) ? ?(G?) ? c log log ?(G?), where c is a constant. Then G? ? G? satisfies Hadwiger's conjecture.

In fact, in the special case where ?(G?) = ?(G?), we give a different (and simpler) proof to show that G? ? G? satisfies Hadwiger's conjecture. As a consequence, we show that Hadwiger's conjecture is true for G? (Cartesian product of G taken d times) for any graph G, if d ? 2. This settles a question asked by Chandran and Sivadasan [2]. (They had shown that Hadwiger's conjecture is true for G? for any graph G, if d ? 3.) We also improve a lower bound proved by Chandran and Sivadasan on the Hadwiger number of Hamming graphs.