Counterexamples to Hedetniemi's conjecture (Q2274002)

The chromatic number \(\chi(G)\) of a graph \(G\) is the least number of colours required to colour the vertices of \(G\) such that adjacent vertices receive different colours. The tensor product of finite simple graphs \(G\) and \(H\), denoted by \(G \times H\), is the graph with vertex set \(V(G)\times V(H)\) such that \((u,v)\) and \((x,y)\) are adjacent if and only if \(u\) and \(x\) are adjacent in \(G\) and \(v\) and \(y\) are adjacent in \(H\). It is easy to see that \(\chi(G \times H) \leq \min\{\chi(G), \chi(H)\}\). \textit{S. T. Hedetniemi} [Homomorphisms of graphs and automata. Techn. Rep. 0310544-T, Ann Arbor, MI: University of Michigan (1966)] conjectured that equality holds for all \(G\) and \(H\). This important conjecture has attracted much attention in more than five decades, and it has been confirmed in many special cases. In this paper, the author disproves this conjecture by showing the existence of infinitely many counterexamples. The strong product \(G \boxtimes H\) is the graph with vertex set \(V(G)\times V(H)\) such that \((u,v)\) and \((x,y)\) are adjacent if and only if one of the following holds: \(u=x\) and \(v\) and \(y\) are adjacent in \(H\); \(v=y\) and \(u\) and \(x\) are adjacent in \(G\); \(u\) and \(x\) are adjacent in \(G\) and \(v\) and \(y\) are adjacent in \(H\). Given a finite graph \(\Gamma\) (possibly with loops) and a positive integer \(c\), the exponential graph \(\mathcal E_{c}(\Gamma)\) is the graph with all mappings \(V(\Gamma) \rightarrow \{1, 2, \ldots, c\}\) as vertices such that two distinct mappings \(\phi\), \(\psi\) are adjacent if and only if the condition \(\phi(u) \neq \psi(v)\) holds whenever there is an edge of \(\Gamma\) between \(u\) and \(v\). The author proved that, for \(c = \lceil 3.1q \rceil\) with \(q\) a sufficiently large integer, and for any graph \(G\) with girth at least \(6\) and fractional chromatic number strictly greater than \(3.1\) (the existence of \(G\) is guaranteed by a classic result of \textit{P. Erdős} [Can. J. Math. 11, 34--38 (1959; Zbl 0084.39602)]), the graph \((G \boxtimes K_{q}) \times\mathcal E_{c}(G \boxtimes K_{q})\) is a counterexample to Hedetniemi's conjecture, where \(K_{q}\) is the complete graph of order \(q\).