# MPI-I-2004-1-006

## On the Hadwiger's conjecture for graph products

### Chandran, L. Sunil and Sivadasan, Naveen

**MPI-I-2004-1-006**. ** **2004, 12 pages. | Status:** **available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:

The Hadwiger number m(G) of a graph G is the

largest integer h such that the complete graph on h nodes is a minor

of G. Equivalently, it is the largest integer such

that any graph on at most m(G) nodes is a minor of G.

The Hadwiger's conjecture states that for any graph G, m(G) >= chi(G),

where

chi(G) is the chromatic number of G. It is well-known

that for any connected undirected graph G, there exists a unique prime

factorization with respect to Cartesian graph products.

If the unique prime factorization of G is given as

G1 X G2 X ... X Gk, where each Gi is prime,

then we say that the product dimension of G is k.

Such a factorization can be computed efficiently.

In this paper, we study the Hadwiger's conjecture for graphs in terms

of their prime factorization.

We show that the Hadwiger's conjecture is true for a graph G if

the product dimension of G is at least 2log(chi(G)) + 3.

In fact, it is enough for G to have a connected graph M as a minor

whose product dimension is at

least 2log(chi(G)) + 3, for G to satisfy the Hadwiger's conjecture.

We show also that

if a graph G is isomorphic to F^d for some F, then

mr(G) >= chi(G)^{\lfloor \frac{d-1}{2} \rfloor}, and thus

G satisfies the Hadwiger's conjecture when d >= 3.

For sufficiently large d, our lower bound is exponentially higher

than what is implied by the Hadwiger's conjecture.

Our approach also yields (almost) sharp lower bounds for the

Hadwiger number of well-known graph products like d--dimensional hypercubes,

Hamming graphs and the d--dimensional grids. In particular, we show that

for a d--dimensional hypercube Hd,

$2^{\lfloor\frac{d-1}{2}\rfloor} <= m(Hd) <= 2^{\frac{d}{2}}\sqrt{d} +1$.

We also derive similar bounds for G^d for almost all

G with n nodes and at least nlog(n) edges.

Acknowledgement:** **

References to related material:

To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |

| 137 KBytes |

Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView |

**URL to this document: **http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/2004-1-006

**BibTeX**
`@TECHREPORT{``ChandranSivadasan2004``,`

` AUTHOR = {Chandran, L. Sunil and Sivadasan, Naveen},`

` TITLE = {On the Hadwiger's conjecture for graph products},`

` TYPE = {Research Report},`

` INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},`

` ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},`

` NUMBER = {MPI-I-2004-1-006},`

` YEAR = {2004},`

` ISSN = {0946-011X},`

`}`