Counterexamples to Hedetniemi's conjecture and infinite Boolean lattices

Claude Tardif

Commentationes Mathematicae Universitatis Carolinae (2022)

  • Volume: 62 63, Issue: 3, page 315-327
  • ISSN: 0010-2628

Abstract

top
We prove that for any c ≥ 5 , there exists an infinite family ( G n ) n ∈ ℕ of graphs such that χ ( G n ) > c for all n ∈ ℕ and χ ( G m × G n ) ≤ c for all m ≠ 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 ≥ 5 .

How to cite

top

Tardif, Claude. "Counterexamples to Hedetniemi's conjecture and infinite Boolean lattices." Commentationes Mathematicae Universitatis Carolinae 62 63.3 (2022): 315-327. <http://eudml.org/doc/299041>.

@article{Tardif2022,
abstract = {We prove that for any $c \ge 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) \le c$ for all $m \ne 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 \ge 5$.},
author = {Tardif, Claude},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {categorical product; graph colouring; Hedetniemi's conjecture},
language = {eng},
number = {3},
pages = {315-327},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {Counterexamples to Hedetniemi's conjecture and infinite Boolean lattices},
url = {http://eudml.org/doc/299041},
volume = {62 63},
year = {2022},
}

TY - JOUR
AU - Tardif, Claude
TI - Counterexamples to Hedetniemi's conjecture and infinite Boolean lattices
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 2022
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 62 63
IS - 3
SP - 315
EP - 327
AB - We prove that for any $c \ge 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) \le c$ for all $m \ne 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 \ge 5$.
LA - eng
KW - categorical product; graph colouring; Hedetniemi's conjecture
UR - http://eudml.org/doc/299041
ER -

References

top
  1. Alishahi M., Hajiabolhassan H., 10.1016/j.disc.2018.02.007, Discrete Math. 341 (2018), no. 5, 1316–1324. MR3777048DOI10.1016/j.disc.2018.02.007
  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., 10.1016/0012-365X(94)00298-W, Discrete Math. 152 (1996), no. 1–3, 125–139. MR1388636DOI10.1016/0012-365X(94)00298-W
  4. El-Zahar M., Sauer N. W., 10.1007/BF02579374, Combinatorica 5 (1985), no. 2, 121–126. MR0815577DOI10.1007/BF02579374
  5. Godsil C., Roberson D. E., Šámal R., Severini S., 10.1007/s00493-014-3132-1, Combinatorica 36 (2016), no. 4, 395–415. MR3537033DOI10.1007/s00493-014-3132-1
  6. Gyárfás A., Jensen T., Stiebitz M., 10.1002/jgt.10165, J. Graph Theory 46 (2004), no. 1, 1–14. MR2051464DOI10.1002/jgt.10165
  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. MR1468789
  8. Hajiabolhassan H., 10.1016/j.disc.2009.01.004, Discrete Math. 309 (2009), no. 13, 4299–4305. MR2519165DOI10.1016/j.disc.2009.01.004
  9. Hajiabolhassan H., Taherkhani A., 10.37236/289, Electron. J. Combin. 17 (2010), no. 1, Research Paper 17, 16 pages. MR2587748DOI10.37236/289
  10. He X., Wigderson Y., 10.1016/j.jctb.2020.03.003, J. Combin. Theory Ser. B 146 (2021), 485–494. MR4177963DOI10.1016/j.jctb.2020.03.003
  11. Hedetniemi S. T., Homomorphisms of Graphs and Automata, Thesis Ph.D., University of Michigan, Michigan, 1966. MR2615860
  12. Shitov Y., Counterexamples to Hedetniemi's conjecture, Ann. of Math. (2) 190 (2019), no. 2, 663–667. MR3997132
  13. Simonyi G., Tardos G., 10.1007/s00493-006-0034-x, Combinatorica 26 (2006), no. 5, 587–626. MR2279672DOI10.1007/s00493-006-0034-x
  14. Simonyi G., Zsbán A., On topological relaxations of chromatic conjectures, European J. Combin. 31 (2010), no. 8, 2110–2119. MR2718285
  15. Tardif C., 10.1007/s11083-010-9162-4, Order 28 (2011), no. 2, 181–191. MR2819218DOI10.1007/s11083-010-9162-4
  16. Tardif C., 10.1007/s00493-021-4781-5, Combinatorica 42 (2022), no. 2, 301–308. MR4426302DOI10.1007/s00493-021-4781-5
  17. Tardif C., Zhu X., 10.1016/S0012-365X(01)00102-9, Algebraic and topological methods in graph theory, Discrete Math. 244 (2002), no. 1–3, 461–471. MR1844054DOI10.1016/S0012-365X(01)00102-9
  18. Tardif C., Zhu X., 10.37236/8787, Electron. J. Combin. 26 (2019), no. 4, Paper No. 4.32, 5 pages. MR4039338DOI10.37236/8787
  19. Wrochna M., 10.1016/j.jctb.2019.02.008, J. Combin. Theory Ser. B 139 (2019), 267–295. MR4010192DOI10.1016/j.jctb.2019.02.008
  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. MR1609464
  22. Zhu X., 10.1016/j.ejc.2011.03.004, European J. Combin. 32 (2011), no. 7, 1168–1175. MR2825542DOI10.1016/j.ejc.2011.03.004
  23. Zhu X., A note on the Poljak–Rödl function, Electron. J. Combin. 27 (2020), no. 3, Paper No. 3.2, 4 pages. MR4245115
  24. Zhu X., 10.1016/j.jctb.2020.09.005, J. Combin. Theory Ser. B 146 (2021), 141–150. MR4153236DOI10.1016/j.jctb.2020.09.005

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.