The $\chi$-Ramsey problem for triangle-free graphs

Abstract

In 1967, Erdős asked for the greatest chromatic number, $f(n)$, amongst all $n$-vertex, triangle-free graphs. An observation of Erdős and Hajnal together with Shearer's classical upper bound for the off-diagonal 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.

13 pages. This version contains minor revisions and a bound in terms of genus that follows from our main results

References in corpus (2)

• Graph structure via local occupancy
• Independent transversals in bipartite correspondence-covers