Geodesic
Coloring digraphs by iterated antichains
Commentationes Mathematicae Universitatis Carolinae, Tome 32 (1991) no. 2, pp. 209-212 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
Classification : 05C15, 06A06, 06A07, 06A10
Keywords: graph product; chromatic number; antichain 
@article{CMUC_1991_32_2_a0,
     author = {Poljak, Svatopluk},
     title = {Coloring digraphs by iterated antichains},
     journal = {Commentationes Mathematicae Universitatis Carolinae},
     pages = {209--212},
     year = {1991},
     volume = {32},
     number = {2},
     mrnumber = {1137780},
     zbl = {0758.05053},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMUC_1991_32_2_a0/}
}
TY  - JOUR
AU  - Poljak, Svatopluk
TI  - Coloring digraphs by iterated antichains
JO  - Commentationes Mathematicae Universitatis Carolinae
PY  - 1991
SP  - 209
EP  - 212
VL  - 32
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/CMUC_1991_32_2_a0/
LA  - en
ID  - CMUC_1991_32_2_a0
ER  - 
%0 Journal Article
%A Poljak, Svatopluk
%T Coloring digraphs by iterated antichains
%J Commentationes Mathematicae Universitatis Carolinae
%D 1991
%P 209-212
%V 32
%N 2
%U http://geodesic.mathdoc.fr/item/CMUC_1991_32_2_a0/
%G en
%F CMUC_1991_32_2_a0
Poljak, Svatopluk. Coloring digraphs by iterated antichains. Commentationes Mathematicae Universitatis Carolinae, Tome 32 (1991) no. 2, pp. 209-212. http://geodesic.mathdoc.fr/item/CMUC_1991_32_2_a0/

[D] 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 | Zbl

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

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

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

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

[HHMN] Häggkvist R., Hell P., Miller D.J., Neumann Lara V.: On the multiplicative graphs and the product conjecture. Combinatorica 8 (1988), 63-74. | MR

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

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