| Title:
|
The chromatic number of the product of two graphs is at least half the minimum of the fractional chromatic numbers of the factors (English) |
| Author:
|
Tardif, Claude |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
42 |
| Issue:
|
2 |
| Year:
|
2001 |
| Pages:
|
353-355 |
| . |
| Category:
|
math |
| . |
| 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) \}$. (English) |
| Keyword:
|
Hedetniemi's conjecture |
| Keyword:
|
(fractional) chromatic number |
| MSC:
|
05C15 |
| idZBL:
|
Zbl 1050.05057 |
| idMR:
|
MR1832153 |
| . |
| Date available:
|
2009-01-08T19:10:35Z |
| Last updated:
|
2012-04-30 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/119249 |
| . |
| Reference:
|
[1] El-Zahar M., Sauer N.: The chromatic number of the product of two $4$-chromatic graphs is $4$.Combinatorica 5 (1985), 121-126. Zbl 0575.05028, MR 0815577 |
| Reference:
|
[2] Hedetniemi S.H.: Homomorphisms of graphs and automata.University of Michigan Technical Report 03105-44-T, 1966. |
| Reference:
|
[3] Poljak S.: Coloring digraphs by iterated antichains.Comment. Math. Univ. Carolinae 32 (1991), 209-212. Zbl 0758.05053, MR 1137780 |
| Reference:
|
[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 |
| Reference:
|
[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. Zbl 0891.05003, MR 1481157 |
| Reference:
|
[6] Zhu X.: A survey on Hedetniemi's conjecture.Taiwanese J. Math. 2 (1998), 1-24. Zbl 0906.05024, MR 1609464 |
| . |
