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.