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


Leave a Reply

Please log in using one of these methods to post your comment: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s