Pokrovskiy, A;
Sudakov, B;
(2017)
Ramsey goodness of paths.
Journal of Combinatorial Theory, Series B
, 122
pp. 384-390.
10.1016/j.jctb.2016.06.009.
Preview |
Text
1512.07874v3.pdf - Accepted Version Download (111kB) | Preview |
Abstract
Given a pair of graphs G and H, the Ramsey number R(G, H) is the smallest N such that every red-blue coloring of the edges of the complete graph KN contains a red copy of G or a blue copy of H. If graph G is connected, it is well known and easy to show that R(G, H) ≥ (|G|−1)(χ(H)−1)+σ(H), where χ(H) is the chromatic number of H and σ the size of the smallest color class in a χ(H)- coloring of H. A graph G is called H-good if R(G, H) = (|G| − 1)(χ(H) − 1) + σ(H). The notion of Ramsey goodness was introduced by Burr and Erd˝os in 1983 and has been extensively studied since then. In this short note we prove that n-vertex path Pn is H-good for all n ≥ 4|H|. This proves in a strong form a conjecture of Allen, Brightwell, and Skokan.
| Type: | Article |
|---|---|
| Title: | Ramsey goodness of paths |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1016/j.jctb.2016.06.009 |
| Publisher version: | https://doi.org/10.1016/j.jctb.2016.06.009 |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions. |
| Keywords: | Ramsey numbers, Ramsey goodness, Paths in graphs, Expanders |
| 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/10112662 |
Archive Staff Only
 |
View Item |
