On the chromatic number of the product of graphs. (English) Zbl 0664.05019

Duffus, D.; Sands, B.; Woodrow, R. E.

J. Graph Theory 9, No. 4, 487-495 (1985).

This paper concerns an intriguing conjecture involving vertex colorings of products of graphs. First we specify the product. Given (irreflexive, symmetric) graphs G and H, the product \(G\times H\) has vertex set V(G)\(\times V(H)\) and edges all pairs \(\{\) (g,h),(g’,h’)\(\}\) such that gg’ and hh’ are edges of G and H, respectively.
Given a coloring \(\phi\) of G, there is a natural induced coloring \(\phi\) ’ of \(G\times H\), namely \(\phi '(g,h)=\phi (g)\). Letting \(\chi\) denote the chromatic number, we see that \[ \chi (G\times H)\leq \min (\chi (G),\chi (H)). \] S. T. Hedetniemi [Homomorphisms of graphs and automata, Univ. of Mich. Techn. Rep. 03105-44-T (1966)] conjectured that equality holds for all graphs G and H. An equivalent formulation is Hedetniemi’s conjecture. For all positive n, for all G and H, \[ \chi (G)=\chi (H)=n\quad implies\quad \chi (G\times H)=n. \] We have not been able to settle this conjecture. However, we have verified it in some special cases, and have in the process come across several related questions which seem interesting. This paper presents what we know on this problem.
In section 3 we introduce two conjectures, both stronger than Hedetniemi’s, which have to do with unique colorability, and which we show to hold in certain special cases. In section 4 we outline two less successful approaches to Hedetniemi’s conjecture.
Very recently, M. El-Zahar and N. W. Sauer [Combinatorica 5, 121-126 (1985; Zbl 0575.05028)] have, with a most elegant and ingenious argument, proved Hedetniemi’s conjecture in the case \(n=4\).

MSC:

05C15	Coloring of graphs and hypergraphs
05C99	Graph theory

Keywords:

vertex colorings; products of graphs

Citations:

Zbl 0575.05028

References:

[1]	Bollobás, Canad. J. Math. 28 pp 1340– (1976) · Zbl 0344.05115 · doi:10.4153/CJM-1976-133-5
[2]	Borowiecki, Colloq. Math. 25 pp 49– (1972)
[3]	de Bruijn, Indaga. Math. 13 pp 369– (1951)
[4]	Burr, Ars Combinatoria 1 pp 167– (1976)
[5]	El-Zahar, Combinatorica.
[6]	Farzan, Canad. J. Math. 29 pp 255– (1977) · Zbl 0343.18004 · doi:10.4153/CJM-1977-027-1
[7]	Greenwell, Acta Math. Acad. Sci. Hungar. 25 pp 335– (1974)
[8]	Grötzsch, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math. Natur. Reihe 8 pp 109– (1958)
[9]	Hajós, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math. Natur. Reihe 10 pp 116– (1961)
[10]	Harary, J. Combinatorial Theory 6 pp 264– (1969) · Zbl 0182.57702
[11]	Homomorphisms of graphs and automata. University of Michigan Technical Report 03105-44-T, 1966.
[12]	Hell, Ann. N. Y. Acad. Sci. 328 pp 120– (1979)
[13]	Hell, Ann. N. Y. Acad. Sci. 319 pp 270– (1979)
[14]	Combinatorial Problems and Exercises. North-Holland, Amsterdam (1979).
[15]	Miller, Canad. J. Math. 20 pp 1511– (1968) · Zbl 0167.21902 · doi:10.4153/CJM-1968-151-x
[16]	Mycielski, Colloq. Math. 3 pp 161– (1955)
[17]	and , Products of graphs and their applications. Graph Theory, Ĺagáw 1981, Lecture Notes in Mathematics 1018, Springer, Berlin (1983), pp. 151–160.
[18]	Osterweil, Discrete Math. 8 pp 56– (1974)
[19]	Poljak, J. Combinatorial Theory Ser. B 31 pp 190– (1981)
[20]	Toft, Studia Sci. Math. Hungar. 5 pp 461– (1970)
[21]	Turzik, Comment Math. Univ. Carolinae 24 pp 461– (1983)
[22]	Weichsel, Proc. Amer. Math. Soc. 13 pp 47– (1962)
[23]	Welzl, J. Combinatorial Theory Ser. B 37 pp 235– (1984)