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 G □ H of graphs. As the main result of this paper, we prove that η(G₁ □ G₂) ≥ h√(1 - o(1)) 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 G = G₁ □ G₂ □ ... □ G_k 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 ₁ and G₂ be two graphs such that χ(G₁) ≥ χ(G₂) - c log^1.5 (χ(G₁)), where c is a constant. Then G₁ □ G₂ 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).