Coloring digraphs by iterated antichains
Poljak, Svatopluk
Commentationes Mathematicae Universitatis Carolinae, Tome 32 (1991), p. 209-212 / Harvested from Czech Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 1991-01-01
Classification:  05C15,  06A06,  06A07,  06A10 
@article{116957,
     author = {Svatopluk Poljak},
     title = {Coloring digraphs by iterated antichains},
     journal = {Commentationes Mathematicae Universitatis Carolinae},
     volume = {32},
     year = {1991},
     pages = {209-212},
     zbl = {0758.05053},
     mrnumber = {1137780},
     language = {en},
     url = {http://dml.mathdoc.fr/item/116957}
}

Poljak, Svatopluk. Coloring digraphs by iterated antichains. Commentationes Mathematicae Universitatis Carolinae, Tome 32 (1991) pp. 209-212. http://gdmltest.u-ga.fr/item/116957/

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. | MR 0115940 | Zbl 0096.00601

Duffus D.; Sands B.; Woodrow R. On the chromatic number of the product of graphs, J. Graph Theory 9 (1985), 487-495. (1985) | MR 0890239 | Zbl 0664.05019

El-Zahar M; Sauer N. The chromatic number of the product of two four-chromatic graphs is four, Combinatorica 5 (1985), 121-126. (1985) | MR 0815577

Hedetniemi S. Homomorphisms of graphs and automata, University of Michigan Technical Report 03105-44-T, 1966.

Harner C.C.; Entringer R.C. Arc coloring of digraphs, J. Combinatorial Theory Ser. B 13 (1972), 219-225. (1972) | MR 0313101

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) | MR 0951994

Poljak S.; Rödl V. On the arc chromatic number of a digraph, J. Combinatorial Theory Ser. B 31 (1981), 190-198. (1981) | MR 0630982

Turzík D. A note on chromatic number of direct product of graphs, Comment. Math. Univ. Carolinae 24 (1983), 461-463. (1983) | MR 0730141