| 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:
|
2024-10-04 |
| 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 |
| . |
