Article
Full entry |
PDF
(0.1 MB)
Feedback
PDF
(0.1 MB)
Feedback
Keywords:
Hedetniemi's conjecture; (fractional) chromatic number
Hedetniemi's conjecture; (fractional) chromatic number
Summary:
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) \}$.
References:
[1] El-Zahar M., Sauer N.: The chromatic number of the product of two $4$-chromatic graphs is $4$. Combinatorica 5 (1985), 121-126. MR 0815577 | Zbl 0575.05028
[2] Hedetniemi S.H.: Homomorphisms of graphs and automata. University of Michigan Technical Report 03105-44-T, 1966.
[3] Poljak S.: Coloring digraphs by iterated antichains. Comment. Math. Univ. Carolinae 32 (1991), 209-212. MR 1137780 | Zbl 0758.05053
[4] Poljak S., Rödl V.: On the arc-chromatic number of a digraph. J. Combin. Theory Ser. B 31 (1981), 339-350. MR 0630982
[5] Scheinerman E.R., Ullman D.H.: 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
[6] Zhu X.: A survey on Hedetniemi's conjecture. Taiwanese J. Math. 2 (1998), 1-24. MR 1609464 | Zbl 0906.05024
Search
Partner of
