The chromatic number of the product of 14-chromatic graphs can be 13 (Q2151188)

In this paper, the author refutes Hedetniemi's conjecture for even small chromatic numbers. He called a graph \(K\) multiplicative if it satisfies the following property: If \(G\times H\) admits a homomorphism (i.e., an edge-preserving map) to \(K\), then \(G\) or \(H\) admits a homomorphism to \(K\) (the product is the categorical product). Hedetniemi's conjecture is the statement that the complete graph \(K_n\) is multiplicative for every \(n\). The main result of this paper is the following: For \(n\geq 13\), \(K_n\) is not multiplicative, i.e., there exist graphs with chromatic number larger than \(n\) whose product has chromatic number \(n\). The construction is an adaptation of the construction of counterexamples to Hedetniemi's conjecture devised by \textit{Y. Shitov} [Ann. Math. (2) 190, No. 2, 663--667 (2019; Zbl 1451.05087)], and adapted by \textit{X. Zhu} [J. Comb. Theory, Ser. B 146, 141--150 (2021; Zbl 1457.05095)] to graphs with relatively small chromatic numbers. The new tools introduced here are graphs with minimal colorings that are ``wide'' in the sense of \textit{G. Simonyi} and \textit{G. Tardos} [Combinatorica 26, No. 5, 587--626 (2006; Zbl 1121.05050)], and generalised Mycielskians to settle the case \(n= 13\).