Davies, Ewan;
Illingworth, Freddie;
(2022)
The X-Ramsey Problem for Triangle-Free Graphs.
SIAM Journal on Discrete Mathematics
, 36
(2)
pp. 1124-1134.
10.1137/21m1437573.
Preview |
Text
chi_Ramsey_SIDMA.pdf - Published Version Download (363kB) | Preview |
Abstract
In 1967, Erd\H os asked for the greatest chromatic number, f(n), amongst all n-vertex, triangle-free graphs. An observation of Erd\H os 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\surd 2+o(1))\sqrt{} n/ log n. We improve this bound by a factor \surd 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 et al. [Electron. J. Combin., 27 (2020), P2.34].
| Type: | Article |
|---|---|
| Title: | The X-Ramsey Problem for Triangle-Free Graphs |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1137/21m1437573 |
| Publisher version: | http://dx.doi.org/10.1137/21m1437573 |
| Language: | English |
| Additional information: | This version is the version of record. For information on re-use, please refer to the publisher’s terms and conditions. |
| Keywords: | Science & Technology, Physical Sciences, Mathematics, Applied, Mathematics, colorings and list colorings, Ramsey problems, extremal graph theory, CHROMATIC NUMBER |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10189639 |
Archive Staff Only
 |
View Item |
