Article in press
Authors:
Title:
Chromatic Ramsey numbers of generalised Mycielski graphs
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2022-09-22 , Revised: 2023-04-08 , Accepted: 2023-04-13 , Available online: 2023-05-24 , https://doi.org/10.7151/dmgt.2499
Abstract:
We revisit the Burr-Erdős-Lovász conjecture on chromatic Ramsey numbers.
We show that it admits a proof based on the Lovász $\vartheta$ parameter
in addition to the proof of Xuding Zhu based on the fractional chromatic number.
However, there are no proofs based on topological lower bounds on chromatic numbers,
because the chromatic Ramsey numbers of generalised Mycielski graphs are too large.
We show that the $4$-chromatic generalised Mycielski graphs other than $K_4$ all have
chromatic Ramsey number $14$, and that the $n$-chromatic generalised Mycielski graphs
all have chromatic Ramsey number at least $2^{n/4}$.
Keywords:
chromatic Ramsey numbers, fractional chromatic numbers, Lovász $\vartheta$ parameter, box complexes, generalised Mycielski graphs
References:
- S.A. Burr, P. Erdős and L. Lovász, On graphs of Ramsey type, Ars Combin. 1 (1976) 167–190.
- D. Duffus, B. Sands and R.E. Woodrow, On the chromatic number of the product of graphs, J. Graph Theory 9 (1985) 487–495.
https://doi.org/10.1002/jgt.3190090409 - C. Godsil, D.E. Roberson, R. Šámal and S. Severini, Sabidussi versus Hedetniemi for three variations of the chromatic number, Combinatorica 36 (2016) 395–415.
https://doi.org/10.1007/s00493-014-3132-1 - C. Godsil, D.E. Roberson, B. Rooney, R. Šámal and A. Varvitsiotis, Vector coloring the categorical product of graphs, Math. Program. 182 (2020) 275–314.
https://doi.org/10.1007/s10107-019-01393-0 - S. Hedetniemi, Homomorphisms of graphs and automata, Technical Report 03105-44-T, University of Michigan (1966).
- L. Lovász, Kneser's conjecture, chromatic number, and homotopy, J. Combin. Theory Ser. A 25 (1978) 319–324.
https://doi.org/10.1016/0097-3165(78)90022-5 - T. Matsushita, $\mathbb{Z}_2$-indices and Hedetniemi's conjecture, Discrete Comput. Geom. 62 (2019) 662–673.
https://doi.org/10.1007/s00454-019-00090-1 - N. Paul and C. Tardif, The chromatic Ramsey number of odd wheels, J. Graph Theory 69 (2012) 198–205.
https://doi.org/10.1002/jgt.20575 - Y. Shitov, Counterexamples to Hedetniemi's Conjecture, Ann. of Math. (2) 190 (2019) 663–667.
https://doi.org/10.4007/annals.2019.190.2.6 - G. Simons, C. Tardif and D. Wehlau, Generalised Mycielski graphs, signature systems, and bounds on chromatic numbers, J. Combin. Theory Ser. B 122 (2017) 776–793.
https://doi.org/10.1016/j.jctb.2016.09.007 - G. Simonyi and G. Tardos, Local chromatic number, Ky Fan's theorem, and circular colorings, Combinatorica 26 (2006) 587–626.
https://doi.org/10.1007/s00493-006-0034-x - G. Simonyi and A. Zsbán, On topological relaxations of chromatic conjectures, European J. Combin. 31 (2010) 2110–2119.
https://doi.org/10.1016/j.ejc.2010.06.001 - G. Simonyi, C. Tardif and A. Zsbán, Colourful theorems and indices of homomorphism complexes, Electron. J. Combin. 20(1) (2013) #P10.
https://doi.org/10.37236/2302 - M. Stiebitz, Beiträge zur Theorie der färbungskritischen Graphen, Habilitation Thesis (Technische Hochschule Ilmenau, 1985).
- P. Turán, A note of welcome, J. Graph Theory 1 (1977) 7–9.
https://doi.org/10.1002/jgt.3190010105 - M. Wrochna, On inverse powers of graphs and topological implications of Hedetniemi's conjecture, J. Combin. Theory Ser. B 139 (2019) 267–295.
https://doi.org/10.1016/j.jctb.2019.02.008 - X. Zhu, The fractional version of Hedetniemi's conjecture is true, European J. Combin. 32 (2011) 1168–1175.
https://doi.org/10.1016/j.ejc.2011.03.004
Close