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 \square H$$ of graphs.
As the main result of this paper, we prove that $$\eta (G_1 \square G_2) \ge h\sqrt{l}\left (1 - o(1) \right )$$ for any two graphs G 1 and G 2 with η(G 1) = h and η(G 2) = 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_1 \square G_2 \square ... \square 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 1 and G 2 be two graphs such that χ(G 1) ≥ χ(G 2) ≥ c log1.5(χ(G 1)), where c is a constant. Then $$G_1 \square 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 [2]. (They had shown that the Hadiwger’s conjecture is true for G d if d ≥ 3).