Mathematics – Combinatorics
Scientific paper
2005-05-22
Mathematics
Combinatorics
10 pages, 2 figures, major update: lower and upper bound proofs have been revised. The bounds are now asymptotically tight
Scientific paper
The Hadwiger number mr(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, mr(G) >= chi(G), where chi(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 mr(G_1 [] G_2) >= h\sqrt{l}(1 - o(1)) for any two graphs G_1 and G_2 with mr(G_1) = h and mr(G_2) = l. We show that the above lower bound is asymptotically best possible. 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 the (unique) prime factorization of G be given by G_1 [] G_2 [] ... [] G_k. Then G satisfies Hadwiger's conjecture if k >= 2.log(log(chi(G))) + c', where c' is a constant. This improves the 2.log(chi(G))+3 bound of Chandran and Sivadasan. 2. Let G_1 and G_2 be two graphs such that chi(G_1) >= chi(G_2) >= c.log^{1.5}(chi(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 (They had shown that the Hadiwger's conjecture is true for G^d if d >= 3.)
Chandran Sunil L.
Kostochka Alexandr
Raju Krishnam J.
No associations
LandOfFree
Hadwiger Number and the Cartesian Product Of Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Hadwiger Number and the Cartesian Product Of Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hadwiger Number and the Cartesian Product Of Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-79718