# zbMATH — the first resource for mathematics

Counterexamples to Hedetniemi’s conjecture. (English) Zbl 1451.05087
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)\}$$. 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 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$$.

##### MSC:
 05C15 Coloring of graphs and hypergraphs 05C76 Graph operations (line graphs, products, etc.)
Full Text:
##### References:
  Burr, S. A.; Erd\H{o}s, P.; Lovasz, L., On graphs of {R}amsey type, Ars Combinatoria. Ars Combinatoria, 1, 167-190, (1976) · Zbl 0333.05120  Duffus, D.; Sands, B.; Woodrow, R. E., On the chromatic number of the product of graphs, J. Graph Theory. Journal of Graph Theory, 9, 487-495, (1985) · Zbl 0664.05019  El-Zahar, M.; Sauer, N. W., The chromatic number of the product of two {$$4$$}-chromatic graphs is {$$4$$}, Combinatorica. Combinatorica. An International Journal of the J\'{a}nos Bolyai Mathematical Society, 5, 121-126, (1985) · Zbl 0575.05028  Erd\H{o}s, P., Graph theory and probability, Canadian J. Math.. Canadian Journal of Mathematics. Journal Canadien de Math\'{e}matiques, 11, 34-38, (1959) · Zbl 0084.39602  H\`‘{a}ggkvist, R.; Hell, P.; Miller, D. J.; Neumann Lara, V., On multiplicative graphs and the product conjecture, Combinatorica. Combinatorica. An International Journal of the J\'’{a}nos Bolyai Mathematical Society, 8, 63-74, (1988) · Zbl 0657.05028  Hajiabolhassan, Hossein; Meunier, Fr\'{e}d\'{e}ric, Hedetniemi’s conjecture for {K}neser hypergraphs, J. Combin. Theory Ser. A. Journal of Combinatorial Theory. Series A, 143, 42-55, (2016) · Zbl 1342.05094  Hajnal, A., The chromatic number of the product of two {$$\aleph_1$$}-chromatic graphs can be countable, Combinatorica. Combinatorica. An International Journal of the J\'{a}nos Bolyai Mathematical Society, 5, 137-139, (1985) · Zbl 0575.05029  Hedetniemi, Stephen Travis, Homomorphisms of Graphs and Automata, 92 pp., (1966)  Klav\v{z}ar, Sandi, Coloring graph products—a survey, Discrete Math.. Discrete Mathematics, 155, 135-145, (1996) · Zbl 0857.05035  Poljak, S.; R\"{o}dl, V., On the arc-chromatic number of a digraph, J. Combin. Theory Ser. B. Journal of Combinatorial Theory. Series B, 31, 190-198, (1981) · Zbl 0472.05024  Sauer, Norbert, Hedetniemi’s conjecture—a survey, Discrete Math.. Discrete Mathematics, 229, 261-292, (2001) · Zbl 0971.05050  Tardif, Claude, Multiplicative graphs and semi-lattice endomorphisms in the category of graphs, J. Combin. Theory Ser. B. Journal of Combinatorial Theory. Series B, 95, 338-345, (2005) · Zbl 1078.05081  Tardif, Claude, Hedetniemi’s conjecture, 40 years later, Graph Theory Notes N. Y.. Graph Theory Notes of New York, 54, 46-57, (2008)  Rinot, Assaf, Hedetniemi’s conjecture for uncountable graphs, J. Eur. Math. Soc. (JEMS). Journal of the European Mathematical Society (JEMS), 19, 285-298, (2017) · Zbl 1423.03238  Valencia-Pabon, Mario; Vera, Juan, Independence and coloring properties of direct products of some vertex-transitive graphs, Discrete Math.. Discrete Mathematics, 306, 2275-2281, (2006) · Zbl 1111.05040  Welzl, Emo, Symmetric graphs and interpretations, J. Combin. Theory Ser. B. Journal of Combinatorial Theory. Series B, 37, 235-244, (1984) · Zbl 0547.05058  Wrochna, M., On inverse powers of graphs and topological implications of {H}edetniemi’s conjecture, J. Combin. Theory B, (2019)  Zhu, Xuding, A survey on {H}edetniemi’s conjecture, Taiwanese J. Math.. Taiwanese Journal of Mathematics, 2, 1-24, (1998) · Zbl 0906.05024  Zhu, Xuding, The fractional version of {H}edetniemi’s conjecture is true, European J. Combin.. European Journal of Combinatorics, 32, 1168-1175, (2011) · Zbl 1229.05108
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.