Hadwiger Number and the Cartesian Product Of Graphs
| dc.creator | Chandran, L. Sunil | |
| dc.creator | Kostochka, Alexandr | |
| dc.creator | Raju, J. Krishnam | |
| dc.date | 2005-05-22 | |
| dc.date | 2007-11-14 | |
| dc.date.accessioned | 2026-07-07T08:42:43Z | |
| dc.date.available | 2026-07-07T08:42:43Z | |
| dc.description | 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.) | |
| dc.description | 10 pages, 2 figures, major update: lower and upper bound proofs have been revised. The bounds are now asymptotically tight | |
| dc.identifier | https://arxiv.org/abs/math/0505455 | |
| dc.identifier | http://arxiv.org/abs/math/0505455 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/142064 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C83 | |
| dc.title | Hadwiger Number and the Cartesian Product Of Graphs | |
| dc.type | text |