Hadwiger number and the Cartesian product of graphs

L. Sunil Chandran, Alexandr Kostochka, J. Krishnam Raju

Research output: Contribution to journalArticlepeer-review


The Hadwiger number η(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, η(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 η(G1 □ G2) ≥ h√(1 - o(1)) for any two graphs G1 and G2 with η(G2) = h and η(G2) = 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 = G1 □ G2 □ ... □ Gk 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 G2 be two graphs such that χ(G1) ≥ χ(G2) - c log1.5 (χ(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 [2]. (They had shown that the Hadiwger's conjecture is true for Gd if d ≥ 3).

Original languageEnglish (US)
Pages (from-to)291-301
Number of pages11
JournalGraphs and Combinatorics
Issue number4
StatePublished - Sep 2008


  • Chromatic number
  • Graph Cartesian product
  • Hadwiger number
  • Hadwiger's conjecture
  • Minor

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Hadwiger number and the Cartesian product of graphs'. Together they form a unique fingerprint.

Cite this