Article
| Title: | Counterexamples to Hedetniemi's conjecture and infinite Boolean lattices (English) |
| Author: | Tardif, Claude |
| Language: | English |
| Journal: | Commentationes Mathematicae Universitatis Carolinae |
| ISSN: | 0010-2628 (print) |
| ISSN: | 1213-7243 (online) |
| Volume: | 63 |
| Issue: | 3 |
| Year: | 2022 |
| Pages: | 315-327 |
| Summary lang: | English |
| . | |
| Category: | math |
| . | |
| 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$. (English) |
| Keyword: | categorical product |
| Keyword: | graph colouring |
| Keyword: | Hedetniemi's conjecture |
| MSC: | 05C15 |
| idZBL: | Zbl 07655803 |
| idMR: | MR4542792 |
| DOI: | 10.14712/1213-7243.2023.003 |
| . | |
| Date available: | 2023-02-01T12:06:33Z |
| Last updated: | 2023-04-20 |
| Stable URL: | http://hdl.handle.net/10338.dmlcz/151479 |
| . | |
| Reference: | [1] Alishahi M., Hajiabolhassan H.: Altermatic number of categorical product of graphs.Discrete Math. 341 (2018), no. 5, 1316–1324. MR 3777048, 10.1016/j.disc.2018.02.007 |
| Reference: | [2] Baum S., Stiebitz M.: Coloring of Graphs without Short Odd Paths between Vertices of the Same Color Class.Syddansk Universitet, Odense, 2005. |
| Reference: | [3] Duffus D., Sauer N.: Lattices arising in categorial investigations of Hedetniemi's conjecture.Discrete Math. 152 (1996), no. 1–3, 125–139. MR 1388636, 10.1016/0012-365X(94)00298-W |
| Reference: | [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. MR 0815577, 10.1007/BF02579374 |
| Reference: | [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. MR 3537033, 10.1007/s00493-014-3132-1 |
| Reference: | [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. MR 2051464, 10.1002/jgt.10165 |
| Reference: | [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 |
| Reference: | [8] Hajiabolhassan H.: On colorings of graph powers.Discrete Math. 309 (2009), no. 13, 4299–4305. MR 2519165, 10.1016/j.disc.2009.01.004 |
| Reference: | [9] Hajiabolhassan H., Taherkhani A.: Graph powers and graph homomorphisms.Electron. J. Combin. 17 (2010), no. 1, Research Paper 17, 16 pages. MR 2587748, 10.37236/289 |
| Reference: | [10] He X., Wigderson Y.: Hedetniemi's conjecture is asymptotically false.J. Combin. Theory Ser. B 146 (2021), 485–494. MR 4177963, 10.1016/j.jctb.2020.03.003 |
| Reference: | [11] Hedetniemi S. T.: Homomorphisms of Graphs and Automata.Thesis Ph.D., University of Michigan, Michigan, 1966. MR 2615860 |
| Reference: | [12] Shitov Y.: Counterexamples to Hedetniemi's conjecture.Ann. of Math. (2) 190 (2019), no. 2, 663–667. MR 3997132 |
| Reference: | [13] Simonyi G., Tardos G.: Local chromatic number, Ky Fan's theorem and circular colorings.Combinatorica 26 (2006), no. 5, 587–626. MR 2279672, 10.1007/s00493-006-0034-x |
| Reference: | [14] Simonyi G., Zsbán A.: On topological relaxations of chromatic conjectures.European J. Combin. 31 (2010), no. 8, 2110–2119. MR 2718285 |
| Reference: | [15] Tardif C.: Hedetniemi's conjecture and dense Boolean lattices.Order 28 (2011), no. 2, 181–191. MR 2819218, 10.1007/s11083-010-9162-4 |
| Reference: | [16] Tardif C.: The chromatic number of the product of 14-chromatic graphs can be 13.Combinatorica 42 (2022), no. 2, 301–308. MR 4426302, 10.1007/s00493-021-4781-5 |
| Reference: | [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. MR 1844054, 10.1016/S0012-365X(01)00102-9 |
| Reference: | [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. MR 4039338, 10.37236/8787 |
| Reference: | [19] Wrochna M.: On inverse powers of graphs and topological implications of Hedetniemi's conjecture.J. Combin. Theory Ser. B 139 (2019), 267–295. MR 4010192, 10.1016/j.jctb.2019.02.008 |
| Reference: | [20] Wrochna M.: Smaller counterexamples to Hedetniemi's conjecture.available at arXiv:2012.13558 [math.CO] (2020), 9 pages. |
| Reference: | [21] Zhu X.: A survey on Hedetniemi's conjecture.Taiwanese J. Math. 2 (1998), no. 1, 1–24. MR 1609464 |
| Reference: | [22] Zhu X.: The fractional version of Hedetniemi's conjecture is true.European J. Combin. 32 (2011), no. 7, 1168–1175. MR 2825542, 10.1016/j.ejc.2011.03.004 |
| Reference: | [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 |
| Reference: | [24] Zhu X.: Relatively small counterexamples to Hedetniemi's conjecture.J. Combin. Theory Ser. B 146 (2021), 141–150. MR 4153236, 10.1016/j.jctb.2020.09.005 |
| . |
Fulltext not available (moving wall 24 months)
Search
Partner of
