The chromatic number of the product of two graphs is at least half the minimum of the fractional chromatic numbers of the factors

Claude Tardif

Commentationes Mathematicae Universitatis Carolinae (2001)

  • Volume: 42, Issue: 2, page 353-355
  • ISSN: 0010-2628

Abstract

top
One consequence of Hedetniemi’s conjecture on the chromatic number of the product of graphs is that the bound χ ( G × H ) ≥ min { χ f ( G ) , χ f ( H ) } should always hold. We prove that χ ( G × H ) ≥ 1 2 min { χ f ( G ) , χ f ( H ) } .

How to cite

top

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 42.2 (2001): 353-355. <http://eudml.org/doc/248789>.

@article{Tardif2001,
abstract = {One consequence of Hedetniemi’s conjecture on the chromatic number of the product of graphs is that the bound $\chi (G \times H) \ge \min \lbrace \chi _f(G), \chi _f(H) \rbrace $ should always hold. We prove that $\chi (G \times H) \ge \frac\{1\}\{2\} \min \lbrace \chi _f(G), \chi _f(H) \rbrace $.},
author = {Tardif, Claude},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {Hedetniemi's conjecture; (fractional) chromatic number; fractional chromatic number; Hedetniemi's conjecture},
language = {eng},
number = {2},
pages = {353-355},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {The chromatic number of the product of two graphs is at least half the minimum of the fractional chromatic numbers of the factors},
url = {http://eudml.org/doc/248789},
volume = {42},
year = {2001},
}

TY - JOUR
AU - Tardif, Claude
TI - The chromatic number of the product of two graphs is at least half the minimum of the fractional chromatic numbers of the factors
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 2001
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 42
IS - 2
SP - 353
EP - 355
AB - One consequence of Hedetniemi’s conjecture on the chromatic number of the product of graphs is that the bound $\chi (G \times H) \ge \min \lbrace \chi _f(G), \chi _f(H) \rbrace $ should always hold. We prove that $\chi (G \times H) \ge \frac{1}{2} \min \lbrace \chi _f(G), \chi _f(H) \rbrace $.
LA - eng
KW - Hedetniemi's conjecture; (fractional) chromatic number; fractional chromatic number; Hedetniemi's conjecture
UR - http://eudml.org/doc/248789
ER -

References

top
  1. El-Zahar M., Sauer N., The chromatic number of the product of two 4 -chromatic graphs is 4 , Combinatorica 5 (1985), 121-126. (1985) Zbl0575.05028MR0815577
  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. (1991) Zbl0758.05053MR1137780
  4. Poljak S., Rödl V., On the arc-chromatic number of a digraph, J. Combin. Theory Ser. B 31 (1981), 339-350. (1981) MR0630982
  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. Zbl0891.05003MR1481157
  6. Zhu X., A survey on Hedetniemi's conjecture, Taiwanese J. Math. 2 (1998), 1-24. (1998) Zbl0906.05024MR1609464

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.