Coloring digraphs by iterated antichains

Svatopluk Poljak

Commentationes Mathematicae Universitatis Carolinae (1991)

  • Volume: 32, Issue: 2, page 209-212
  • ISSN: 0010-2628

Abstract

top
We show that the minimum chromatic number of a product of two n -chromatic graphs is either bounded by 9, or tends to infinity. The result is obtained by the study of coloring iterated adjoints of a digraph by iterated antichains of a poset.

How to cite

top

Poljak, Svatopluk. "Coloring digraphs by iterated antichains." Commentationes Mathematicae Universitatis Carolinae 32.2 (1991): 209-212. <http://eudml.org/doc/247261>.

@article{Poljak1991,
abstract = {We show that the minimum chromatic number of a product of two $n$-chromatic graphs is either bounded by 9, or tends to infinity. The result is obtained by the study of coloring iterated adjoints of a digraph by iterated antichains of a poset.},
author = {Poljak, Svatopluk},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {graph product; chromatic number; antichain; coloring digraphs; iterated antichains; Lovász-Hedetniemi conjecture; graph product; chromatic number},
language = {eng},
number = {2},
pages = {209-212},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {Coloring digraphs by iterated antichains},
url = {http://eudml.org/doc/247261},
volume = {32},
year = {1991},
}

TY - JOUR
AU - Poljak, Svatopluk
TI - Coloring digraphs by iterated antichains
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 1991
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 32
IS - 2
SP - 209
EP - 212
AB - We show that the minimum chromatic number of a product of two $n$-chromatic graphs is either bounded by 9, or tends to infinity. The result is obtained by the study of coloring iterated adjoints of a digraph by iterated antichains of a poset.
LA - eng
KW - graph product; chromatic number; antichain; coloring digraphs; iterated antichains; Lovász-Hedetniemi conjecture; graph product; chromatic number
UR - http://eudml.org/doc/247261
ER -

References

top
  1. Dilworth R.P., Some combinatorial problems on partially ordered sets, Combinatorial Analysis, R. Bellman and M. Halls (eds.), Proc. Symp. Appl. Math., Amer. Math. Soc., Providence, 1960, 85-90. Zbl0096.00601MR0115940
  2. Duffus D., Sands B., Woodrow R., On the chromatic number of the product of graphs, J. Graph Theory 9 (1985), 487-495. (1985) Zbl0664.05019MR0890239
  3. El-Zahar M, Sauer N., The chromatic number of the product of two four-chromatic graphs is four, Combinatorica 5 (1985), 121-126. (1985) MR0815577
  4. Hedetniemi S., Homomorphisms of graphs and automata, University of Michigan Technical Report 03105-44-T, 1966. 
  5. Harner C.C., Entringer R.C., Arc coloring of digraphs, J. Combinatorial Theory Ser. B 13 (1972), 219-225. (1972) MR0313101
  6. Häggkvist R., Hell P., Miller D.J., Neumann Lara V., On the multiplicative graphs and the product conjecture, Combinatorica 8 (1988), 63-74. (1988) MR0951994
  7. Poljak S., Rödl V., On the arc chromatic number of a digraph, J. Combinatorial Theory Ser. B 31 (1981), 190-198. (1981) MR0630982
  8. Turzík D., A note on chromatic number of direct product of graphs, Comment. Math. Univ. Carolinae 24 (1983), 461-463. (1983) MR0730141

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.