chi_c of product graph

Suppose G = ( V, E ) and H = ( V', E' ). The categorical product G x H has vertex set  V x V' = { (x, x'): x \in V, x' \in V' }, in which  (x, x') is adjacent to  (y, y')  if and only if  x is adjacent to x'  in G  and y is adjacent to y'  in H.  Any (p, q)-coloring f  of G induces a (p, q)-coloring g of  G x H defined as  g(x, x') = f(x).  Therefore  chi_c(G x H) <=  chi_c(G). Similarly, chi_c(G x H) <= chi_c(H).

Conjecture    For any rational p/q,  if  min { chi_c(G),  chi_c(H) } > p/q, then chi_c(G) > p/q.  In other words, chi_c( G x H ) = min { chi_c(G),  chi_c(H) }.

This conjecture first appeared in [Zhu92] as a generalization of Hedetniemi's conjecture.

El-Zahar and Sauer, and Haggkvist, Hell, Miller and Newmann Lara (see [Zhu92] for the references and a discussion about it ) proved that if  min { chi_c(G),  chi_c(H) } = 2 + 1/k, then chi_c( G x H ) = min { chi_c(G),  chi_c(H) }.

Claude Tardif has proved (2004) that if min { chi_c(G),  chi_c(H) } < 4, then chi_c( G x H ) = min { chi_c(G),  chi_c(H) }.

Hedetniemi's Conjecture   For any integer k, if min { chi(G),  chi(H) }  > k, then chi( G x H ) > k.  In other words,  chi( G x H ) = min { chi(G), chi(H) .

See [Zhu98]  for a survey on Hedetniemi's conjecture.