One consequence of Hedetniemi's conjecture on the chromatic number of the product of graphs is that the bound $\chi(G \times H) \geq \min \{ \chi_f(G), \chi_f(H) \}$ should always hold. We prove that $\chi(G \times H) \geq \frac{1}{2} \min \{ \chi_f(G), \chi_f(H) \}$.
@article{119249,
author = {Claude Tardif},
title = {The chromatic number of the product of two graphs is at least half the minimum of the fractional chromatic numbers of the factors},
journal = {Commentationes Mathematicae Universitatis Carolinae},
volume = {42},
year = {2001},
pages = {353-355},
zbl = {1050.05057},
mrnumber = {1832153},
language = {en},
url = {http://dml.mathdoc.fr/item/119249}
}
Tardif, Claude. The chromatic number of the product of two graphs is at least half the minimum of the fractional chromatic numbers of the factors. Commentationes Mathematicae Universitatis Carolinae, Tome 42 (2001) pp. 353-355. http://gdmltest.u-ga.fr/item/119249/
The chromatic number of the product of two $4$-chromatic graphs is $4$, Combinatorica 5 (1985), 121-126. (1985) | MR 0815577 | Zbl 0575.05028
Homomorphisms of graphs and automata, University of Michigan Technical Report 03105-44-T, 1966.
Coloring digraphs by iterated antichains, Comment. Math. Univ. Carolinae 32 (1991), 209-212. (1991) | MR 1137780 | Zbl 0758.05053
On the arc-chromatic number of a digraph, J. Combin. Theory Ser. B 31 (1981), 339-350. (1981) | MR 0630982
Fractional Graph Theory, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, New York, 1997, xviii+211 pp. | MR 1481157 | Zbl 0891.05003
A survey on Hedetniemi's conjecture, Taiwanese J. Math. 2 (1998), 1-24. (1998) | MR 1609464 | Zbl 0906.05024