Article
Full entry |
PDF
(0.1 MB)
Feedback
PDF
(0.1 MB)
Feedback
Keywords:
graph product; chromatic number; antichain
graph product; chromatic number; antichain
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.
References:
[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 0115940 | Zbl 0096.00601
[DSW] Duffus D., Sands B., Woodrow R.: On the chromatic number of the product of graphs. J. Graph Theory 9 (1985), 487-495. MR 0890239 | Zbl 0664.05019
[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
[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 0313101
[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
[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
[T] Turzík D.: A note on chromatic number of direct product of graphs. Comment. Math. Univ. Carolinae 24 (1983), 461-463. MR 0730141
Search
Partner of
