×

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.)

Citations:

Zbl 0084.39602
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] 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
[2] 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 · doi:10.1002/jgt.3190090409
[3] 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 · doi:10.1007/BF02579374
[4] 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 · doi:10.4153/CJM-1959-003-9
[5] 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 · doi:10.1007/BF02122553
[6] 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 · doi:10.1016/j.jcta.2016.05.002
[7] 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 · doi:10.1007/BF02579376
[8] Hedetniemi, Stephen Travis, Homomorphisms of Graphs and Automata, 92 pp., (1966)
[9] Klav\v{z}ar, Sandi, Coloring graph products–a survey, Discrete Math.. Discrete Mathematics, 155, 135-145, (1996) · Zbl 0857.05035 · doi:10.1016/0012-365X(94)00377-U
[10] 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 · doi:10.1016/S0095-8956(81)80024-X
[11] Sauer, Norbert, Hedetniemi’s conjecture–a survey, Discrete Math.. Discrete Mathematics, 229, 261-292, (2001) · Zbl 0971.05050 · doi:10.1016/S0012-365X(00)00213-2
[12] 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 · doi:10.1016/j.jctb.2005.06.002
[13] Tardif, Claude, Hedetniemi’s conjecture, 40 years later, Graph Theory Notes N. Y.. Graph Theory Notes of New York, 54, 46-57, (2008)
[14] 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 · doi:10.4171/JEMS/666
[15] 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 · doi:10.1016/j.disc.2006.04.013
[16] Welzl, Emo, Symmetric graphs and interpretations, J. Combin. Theory Ser. B. Journal of Combinatorial Theory. Series B, 37, 235-244, (1984) · Zbl 0547.05058 · doi:10.1016/0095-8956(84)90056-X
[17] Wrochna, M., On inverse powers of graphs and topological implications of {H}edetniemi’s conjecture, J. Combin. Theory B, (2019) · Zbl 1428.05259 · doi:10.1016/j.jctb.2019.02.008
[18] Zhu, Xuding, A survey on {H}edetniemi’s conjecture, Taiwanese J. Math.. Taiwanese Journal of Mathematics, 2, 1-24, (1998) · Zbl 0906.05024 · doi:10.11650/twjm/1500406890
[19] 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 · doi:10.1016/j.ejc.2011.03.004
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.