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:









Author, Editor

Author(s):

Chandran, L. Sunil
Sivadasan, Naveen

dblp
dblp



Editor(s):





BibTeX Citekey*:

ChandranSivadasan2004

Language:

English

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, Abstract, ©

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:
@TECHREPORT{ChandranSivadasan2004,
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},
}


Entry last modified by Christine Kiesel, 03/02/2010
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Created
08/12/2005 12:13:30 PM
Revision
1.
0.


Editor
Christine Kiesel



Edit Date
12.08.2005 12:15:15



Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section
MPI-I-2004-1-006.ps
View attachments here: