zbMATH — the first resource for mathematics

The chromatic number of the product of two 4-chromatic graphs is 4. (English) Zbl 0575.05028
The product \(G\times H\) of two graphs G and H is the graph whose vertex set is \(V(G)\times V(H)\) and whose edge set consists of all pairs \(((a,b), (\bar a,\bar b))\) such that \((a,\bar a)\) and \((b,\bar b)\) are edges of G and H respectively. The chromatic number of the product is early seen to satisfy the bound \(\chi(G\times H)\leq \min\{\chi(G),\chi(H)\}\). S. Hedetniemi [Homomorphisms of graphs and automata, Univ. of Michigan Technical report 03105-44-T (1966)] has conjectured that equality holds in this bound, verifying this when the right-hand side is 3. The present paper verifies this conjecture when the right-hand side is 4.
Reviewer: J.G.Oxley

05C15 Coloring of graphs and hypergraphs
Full Text: DOI
[1] S. A. Burr, P. Erdos andL. Lovász, On graphs of Ramsey type,Ars Comb. 1 (1976), 167–190.
[2] D. Duffus, B. Sands andR. E. Woodrow, On the Chromatic Number of the Product of Graphs,Journal of Graph Theory, to appear. · Zbl 0664.05019
[3] S. T. Hedetniemi, Homomorphisms of graphs and automata,Univ. of Michigan Technical Report 03105-44-T, 1966.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.