Technical, Research Report @TechReport Technischer-, Forschungsbericht

 Show entries of: this year (2019) | last year (2018) | two years ago (2017) | Notes URL
 Action: login to update Options: Edit Delete Goto entry point

 Author, Editor
 Author(s): Chandran, L. Sunil Sivadasan, Naveen dblp dblp
 Editor(s):

 Title, Institution
 Title*: On the Hadwiger's Conjecture for Graph Products Institution*: Max-Planck-Institut für Informatik Publishers or Institutions Address*: Stuhlsatzenhausweg 85, 66123 Saarbrücken, Germany Type: Research Report

 No, Year, pp.,
 Number*: MPI-I-2004-1-006 Pages*: 12 Month: VG Wort Pages*: Year*: 2004 ISBN/ISSN: 0946-011X DOI:

 Note: (LaTeX) Abstract: The Hadwiger number m(G) of a graph G is the largest integer h such that the complete graph on h nodes is a minor of G. Equivalently, it is the largest integer such that any graph on at most m(G) nodes is a minor of G. The Hadwiger's conjecture states that for any graph G, m(G) >= chi(G), where chi(G) is the chromatic number of G. It is well-known 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 X G2 X ... X Gk, where each Gi is prime, then we say that the product dimension of G is k. Such a factorization can be computed efficiently. In this paper, we study the Hadwiger's conjecture for graphs in terms of their prime factorization. We show that the Hadwiger's conjecture is true for a graph G if the product dimension of G is at least 2log(chi(G)) + 3. In fact, it is enough for G to have a connected graph M as a minor whose product dimension is at least 2log(chi(G)) + 3, for G to satisfy the Hadwiger's conjecture. We show also that if a graph G is isomorphic to F^d for some F, then mr(G) >= chi(G)^{\lfloor \frac{d-1}{2} \rfloor}, and thus G satisfies the Hadwiger's conjecture when d >= 3. For sufficiently large d, our lower bound is exponentially higher than what is implied by the Hadwiger's conjecture. Our 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, $2^{\lfloor\frac{d-1}{2}\rfloor} <= m(Hd) <= 2^{\frac{d}{2}}\sqrt{d} +1$. We also derive similar bounds for G^d for almost all G with n nodes and at least nlog(n) edges. Categories / Keywords: Copyright Message: HyperLinks / References / URLs: Personal Comments: File Upload: Download Access Level: Public

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Audience: Expert Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat

BibTeX Entry:
AUTHOR = {Chandran, L. Sunil and Sivadasan, Naveen},
TITLE = {On the Hadwiger's Conjecture for Graph Products},
PUBLISHER = {AG 1 - Mehlhorn},
YEAR = {2004},
TYPE = {Research Report},
INSTITUTION = {Max-Planck-Institut für Informatik},
NUMBER = {MPI-I-2004-1-006},
PAGES = {12},
ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},
ISBN = {0946-011X},
}