# The Hadwiger’s conjecture

Speaking about graphs, the Hadwiger number (G) of a graph G is the largest integer h such that the complete graph on h nodes K h is a minor of G. Equivalently, it is the largest integer in a way which any graph on at most (G) nodes is a minor of G. The Hadwiger’s conjecture states for any graph G, (G) number of G. It is well-known by mathematicians 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 G 2 ::: G k, where each G i is prime, then we say that the product dimension of G is k. Such a factorization can be computed efficiently.

Studying the Hadwiger’s conjecture for graphs in terms of their prime factorization. It shows the Hadwiger’s conjecture is true for a graph G if the product dimension of G is at least 2 log ( (G)) + 3. In fact, it is enough for

This 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, 2b