2005/05/22 by L. Sunil Chandran, Chandran, L. Sunil, Alexandr Kostochka +3
Computer Science · Mathematics · #05C83 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.math/0505455
openalex publication_date 2005/05/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Hadwiger number mr(G) of a graph G is the largest integer n for which the complete graph Kn 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(G1 [] G2) >= h√(l)(1 - o(1)) for any two graphs G1 and G2 with mr(G1) = h and mr(G2) = 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 G1 [] G2 [] ... [] Gk. 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 G1 and G2 be two graphs such that chi(G1) >= chi(G2) >= c.log1.5(chi(G1)), where c is a constant. Then G1 [] G2 satisfies Hadwiger's conjecture. 3. Hadwiger's conjecture is true for Gd (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 Gd if d >= 3.)