{
  "id": "math/0505455",
  "version": "v3",
  "published": "2005-05-22T14:13:31.000Z",
  "updated": "2007-11-14T03:36:21.000Z",
  "title": "Hadwiger Number and the Cartesian Product Of Graphs",
  "authors": [
    "L. Sunil Chandran",
    "Alexandr Kostochka",
    "J. Krishnam Raju"
  ],
  "comment": "10 pages, 2 figures, major update: lower and upper bound proofs have been revised. The bounds are now asymptotically tight",
  "categories": [
    "math.CO"
  ],
  "abstract": "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.)",
  "revisions": [
    {
      "version": "v3",
      "updated": "2007-11-14T03:36:21.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C83"
    ],
    "keywords": [
      "cartesian product",
      "satisfies hadwigers conjecture",
      "main result",
      "hadwiger number mr",
      "complete graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 10,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2005math......5455C"
    }
  }
}