The $\chi$Ramsey problem for trianglefree graphs
Abstract
In 1967, Erdős asked for the greatest chromatic number, $f(n)$, amongst all $n$vertex, trianglefree graphs. An observation of Erdős and Hajnal together with Shearer's classical upper bound for the offdiagonal Ramsey number $R(3, t)$ shows that $f(n)$ is at most $(2 \sqrt{2} + o(1)) \sqrt{n/\log n}$. We improve this bound by a factor $\sqrt{2}$, as well as obtaining an analogous bound on the list chromatic number which is tight up to a constant factor. A bound in terms of the number of edges that is similarly tight follows, and these results confirm a conjecture of Cames van Batenburg, de Joannis de Verclos, Kang, and Pirot.
 Publication:

arXiv eprints
 Pub Date:
 July 2021
 arXiv:
 arXiv:2107.12288
 Bibcode:
 2021arXiv210712288D
 Keywords:

 Mathematics  Combinatorics;
 05C15;
 05C35 (Primary) 05D10 (Secondary)
 EPrint:
 10 pages