Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
categorical product; graph colouring; Hedetniemi's conjecture
categorical product; graph colouring; Hedetniemi's conjecture
Summary:
We prove that for any $c \geq 5$, there exists an infinite family $(G_n )_{n\in \mathbb{N}}$ of graphs such that $\chi(G_n) > c$ for all $n\in \mathbb{N}$ and $\chi(G_m \times G_n) \leq c$ for all $m \neq n$. These counterexamples to Hedetniemi's conjecture show that the Boolean lattice of exponential graphs with $K_c$ as a base is infinite for $c \geq 5$.
References:
[1] Alishahi M., Hajiabolhassan H.: Altermatic number of categorical product of graphs. Discrete Math. 341 (2018), no. 5, 1316–1324. DOI 10.1016/j.disc.2018.02.007 | MR 3777048
[2] Baum S., Stiebitz M.: Coloring of Graphs without Short Odd Paths between Vertices of the Same Color Class. Syddansk Universitet, Odense, 2005.
[3] Duffus D., Sauer N.: Lattices arising in categorial investigations of Hedetniemi's conjecture. Discrete Math. 152 (1996), no. 1–3, 125–139. DOI 10.1016/0012-365X(94)00298-W | MR 1388636
[4] El-Zahar M., Sauer N. W.: The chromatic number of the product of two $4$-chromatic graphs is $4$. Combinatorica 5 (1985), no. 2, 121–126. DOI 10.1007/BF02579374 | MR 0815577
[5] Godsil C., Roberson D. E., Šámal R., Severini S.: Sabidussi versus Hedetniemi for three variations of the chromatic number. Combinatorica 36 (2016), no. 4, 395–415. DOI 10.1007/s00493-014-3132-1 | MR 3537033
[6] Gyárfás A., Jensen T., Stiebitz M.: On graphs with strongly independent color-classes. J. Graph Theory 46 (2004), no. 1, 1–14. DOI 10.1002/jgt.10165 | MR 2051464
[7] Hahn G., Tardif C.: Graph homomorphisms: structure and symmetry. Graph symmetry, Montreal, 1996, NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci., 497, Kluwer Acad. Publ., Dordrecht, 1997, pages 107–166. MR 1468789
[8] Hajiabolhassan H.: On colorings of graph powers. Discrete Math. 309 (2009), no. 13, 4299–4305. DOI 10.1016/j.disc.2009.01.004 | MR 2519165
[9] Hajiabolhassan H., Taherkhani A.: Graph powers and graph homomorphisms. Electron. J. Combin. 17 (2010), no. 1, Research Paper 17, 16 pages. DOI 10.37236/289 | MR 2587748
[10] He X., Wigderson Y.: Hedetniemi's conjecture is asymptotically false. J. Combin. Theory Ser. B 146 (2021), 485–494. DOI 10.1016/j.jctb.2020.03.003 | MR 4177963
[11] Hedetniemi S. T.: Homomorphisms of Graphs and Automata. Thesis Ph.D., University of Michigan, Michigan, 1966. MR 2615860
[12] Shitov Y.: Counterexamples to Hedetniemi's conjecture. Ann. of Math. (2) 190 (2019), no. 2, 663–667. MR 3997132
[13] Simonyi G., Tardos G.: Local chromatic number, Ky Fan's theorem and circular colorings. Combinatorica 26 (2006), no. 5, 587–626. DOI 10.1007/s00493-006-0034-x | MR 2279672
[14] Simonyi G., Zsbán A.: On topological relaxations of chromatic conjectures. European J. Combin. 31 (2010), no. 8, 2110–2119. MR 2718285
[15] Tardif C.: Hedetniemi's conjecture and dense Boolean lattices. Order 28 (2011), no. 2, 181–191. DOI 10.1007/s11083-010-9162-4 | MR 2819218
[16] Tardif C.: The chromatic number of the product of 14-chromatic graphs can be 13. Combinatorica 42 (2022), no. 2, 301–308. DOI 10.1007/s00493-021-4781-5 | MR 4426302
[17] Tardif C., Zhu X.: The level of nonmultiplicativity of graphs. Algebraic and topological methods in graph theory, Discrete Math. 244 (2002), no. 1–3, 461–471. DOI 10.1016/S0012-365X(01)00102-9 | MR 1844054
[18] Tardif C., Zhu X.: A note on Hedetniemi's conjecture, Stahl's conjecture and the Poljak–Rödl function. Electron. J. Combin. 26 (2019), no. 4, Paper No. 4.32, 5 pages. DOI 10.37236/8787 | MR 4039338
[19] Wrochna M.: On inverse powers of graphs and topological implications of Hedetniemi's conjecture. J. Combin. Theory Ser. B 139 (2019), 267–295. DOI 10.1016/j.jctb.2019.02.008 | MR 4010192
[20] Wrochna M.: Smaller counterexamples to Hedetniemi's conjecture. available at arXiv:2012.13558 [math.CO] (2020), 9 pages.
[21] Zhu X.: A survey on Hedetniemi's conjecture. Taiwanese J. Math. 2 (1998), no. 1, 1–24. MR 1609464
[22] Zhu X.: The fractional version of Hedetniemi's conjecture is true. European J. Combin. 32 (2011), no. 7, 1168–1175. DOI 10.1016/j.ejc.2011.03.004 | MR 2825542
[23] Zhu X.: A note on the Poljak–Rödl function. Electron. J. Combin. 27 (2020), no. 3, Paper No. 3.2, 4 pages. MR 4245115
[24] Zhu X.: Relatively small counterexamples to Hedetniemi's conjecture. J. Combin. Theory Ser. B 146 (2021), 141–150. DOI 10.1016/j.jctb.2020.09.005 | MR 4153236
Search
Partner of
