Hadwiger number and the cartesian product operation on graphs
L. Sunil Chandran and J. Krishnam Raju

IISc-CSA-TR-2005-5
(May 2005)

Available formats: [ps] [ps.gz]

Filed on June 19, 2005
Updated on June 19, 2005



The Hadwiger number $\mr(G)$ of a graph $G$ is defined as the largest
integer $n$ for which the complete graph on $n$ nodes $K_n$ is a minor of G.
Hadwiger conjectured that for any graph $G$, $\mr(G) \ge \chi(G)$,where
$\chi(G)$ is the chromatic number of $G$. In this paper, we investigate
the Hadwiger number with respect to the cartesian product operation on Graphs.

As the main result of this paper, we show that for any
two graphs $G_1$ and $G_2$ with $\mr(G_1) = h$ and
$\mr(G_2) = l$, $\mr(G_1 \cart G_2) \ge \frac{1}{4}(h-\sqrt{l})(\sqrt{l}-2)$.
(Since $G_1 \cart G_2$ is isomorphic to $G_2 \cart G_1$, we can assume without
loss of generality that $h \ge l$).
This lower bound is the best possible (up to a small constant factor), since if
$G_1 = K_h$ and $G_2 = K_l$, $\mr(G_1 \cart G_2) \le 2h\sqrt{l}$. We also show
that $\mr(G_1 \cart G_2)$ doesn't have any upper bound which depends only on
$\mr(G_1)$ and $\mr(G_2)$, by demonstrating graphs $G_1$ and $G_2$ such that
$\mr(G_1)$ and $\mr(G_2)$ are bounded whereas $\mr(G_1 \cart G_2)$ grows with
the number of nodes. (The problem of studying the Hadwiger number with respect
to the cartesian product operation was posed by Z.Miller in 1978.)

As consequences of our main result, we show the following:
\begin{enumerate}
\item Let $G$ be a connected graph. Let the (unique) prime factorization of $G$
be given by $G_1 \cart G_2 \cart ... \cart G_k$. Then
$G$ satisfies Hadwiger's conjecture if $k \ge 2\log{\log{\chi(G)}} + c'$, where
$c'$ is a constant. This improves the $2\log{\chi(G)}+3$ bound given in
\cite{sunns1}.

\item Let $G_1$ and $G_2$ be two graphs such that $\chi(G_1) \ge \chi(G_2) \ge
c{{\log}^{1.5}}(\chi(G_1))$, where $c$ is a constant. Then $G_1 \cart G_2$
satisfies Hadwiger's conjecture.
\end{enumerate}

In fact, in the special case where $\chi(G_1) = \chi(G_2)$ we give a different
(and simpler) proof to show that $G_1 \cart G_2$ satisfies Hadwiger's conjecture.
As a consequence we show that Hadwiger's conjecture is true for $G^d$
(cartesian product of $G$ taken $d$ times) for
any graph $G$, if $d \ge 2$. This settles a question asked by Chandran and Sivadasan
\cite{sunns1}. (They had shown that Hadiwger's conjecture is true for $G^d$ for
any graph $G$, if $d \ge 3$.) We also improve a lower bound proved by
Chandran and Sivadasan on the Hadwiger number of Hamming graphs.\\


Please bookmark this technical report as http://aditya.csa.iisc.ernet.in/TR/2005/5/.

Problems ? Contact techrep@csa.iisc.ernet.in
[Updated at 2009-10-22T06:42Z]