## Abstract

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_{1} □ G_{2}) ≥ h√(1 - o(1)) for any two graphs G_{1} and G_{2} with η(G_{2}) = 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} □ G_{2} □ ... □ 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 log^{1.5} (χ(G_{1})), where c is a constant. Then G_{1} □ 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).

Original language | English (US) |
---|---|

Pages (from-to) | 291-301 |

Number of pages | 11 |

Journal | Graphs and Combinatorics |

Volume | 24 |

Issue number | 4 |

DOIs | |

State | Published - Sep 2008 |

## Keywords

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

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics