Hadwiger Number and the Cartesian Product of Graphs

The Hadwiger number η(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, η(G) ≥ χ(G), where χ(G) is the chromatic number of G. In this paper, we study the Hadwiger number of the Cartesian product of graphs. As the main result of this paper, we prove that for any two graphs G ₁ and G ₂ with η(G ₁) = h and η(G ₂) = l. We show that the above lower bound is asymptotically best possible when h ≥ l. 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 be the (unique) prime factorization of 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 in 2].
2.	Let G 1 and G 2 be two graphs such that χ(G 1) ≥ χ(G 2) ≥ c log1.5(χ(G 1)), where c is a constant. Then 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 2]. (They had shown that the Hadiwger’s conjecture is true for G d if d ≥ 3).

Alexandr Kostochka: Research of this author is supported in part by NSF grant DMS-0650784 and grant 06-01-00694 of the Russian Foundation for Basic Research.