Technical, Research Report
@TechReport
Technischer, Forschungsbericht  
Editor(s):     

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 wellknown
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{d1}{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 wellknown graph products like ddimensional hypercubes,
Hamming graphs and the ddimensional grids. In particular, we show that
for a ddimensional hypercube Hd,
$2^{\lfloor\frac{d1}{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 

MPG Unit:  MaxPlanckInstitut 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 = {MaxPlanckInstitut für Informatik},
NUMBER = {MPII20041006},
PAGES = {12},
ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},
ISBN = {0946011X},
}
Entry last modified by Christine Kiesel, 03/02/2010