# Hadwiger Number and the Cartesian Product Of Graphs

Research paper by **L. Sunil Chandran, Alexandr Kostochka, J. Krishnam Raju**

Indexed on: **13 Nov '07**Published on: **13 Nov '07**Published in: **Mathematics - Combinatorics**

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join for free

#### Abstract

The Hadwiger number mr(G) of a graph G is the largest integer n for which the
complete graph K_n on n vertices is a minor of G. Hadwiger conjectured that for
every graph G, mr(G) >= chi(G), where chi(G) is the chromatic number of G. In
this paper, we study the Hadwiger number of the Cartesian product G [] H of
graphs.
As the main result of this paper, we prove that mr(G_1 [] G_2) >= h\sqrt{l}(1
- o(1)) for any two graphs G_1 and G_2 with mr(G_1) = h and mr(G_2) = l. We
show that the above lower bound is asymptotically best possible. This
asymptotically settles a question of Z. Miller (1978).
As consequences of our main result, we show the following:
1. Let G be a connected graph. Let the (unique) prime factorization of G be
given by G_1 [] G_2 [] ... [] G_k. Then G satisfies Hadwiger's conjecture if k
>= 2.log(log(chi(G))) + c', where c' is a constant. This improves the
2.log(chi(G))+3 bound of Chandran and Sivadasan.
2. Let G_1 and G_2 be two graphs such that chi(G_1) >= chi(G_2) >=
c.log^{1.5}(chi(G_1)), where c is a constant. Then G_1 [] G_2 satisfies
Hadwiger's conjecture.
3. Hadwiger's conjecture is true for G^d (Cartesian product of G taken d
times) for every graph G and every d >= 2. This settles a question by Chandran
and Sivadasan (They had shown that the Hadiwger's conjecture is true for G^d if
d >= 3.)