| Title:
|
Coloring digraphs by iterated antichains (English) |
| Author:
|
Poljak, Svatopluk |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
32 |
| Issue:
|
2 |
| Year:
|
1991 |
| Pages:
|
209-212 |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
graph product |
| Keyword:
|
chromatic number |
| Keyword:
|
antichain |
| MSC:
|
05C15 |
| MSC:
|
06A06 |
| MSC:
|
06A07 |
| MSC:
|
06A10 |
| idZBL:
|
Zbl 0758.05053 |
| idMR:
|
MR1137780 |
| . |
| Date available:
|
2008-10-09T13:11:52Z |
| Last updated:
|
2012-04-30 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/116957 |
| . |
| Reference:
|
[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. Zbl 0096.00601, MR 0115940 |
| Reference:
|
[DSW] Duffus D., Sands B., Woodrow R.: On the chromatic number of the product of graphs.J. Graph Theory 9 (1985), 487-495. Zbl 0664.05019, MR 0890239 |
| Reference:
|
[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 0815577 |
| Reference:
|
[H] Hedetniemi S.: Homomorphisms of graphs and automata.University of Michigan Technical Report 03105-44-T, 1966. |
| Reference:
|
[HE] Harner C.C., Entringer R.C.: Arc coloring of digraphs.J. Combinatorial Theory Ser. B 13 (1972), 219-225. MR 0313101 |
| Reference:
|
[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 0951994 |
| Reference:
|
[PR] Poljak S., Rödl V.: On the arc chromatic number of a digraph.J. Combinatorial Theory Ser. B 31 (1981), 190-198. MR 0630982 |
| Reference:
|
[T] Turzík D.: A note on chromatic number of direct product of graphs.Comment. Math. Univ. Carolinae 24 (1983), 461-463. MR 0730141 |
| . |
