Pokrovskiy, A;
(2017)
Calculating Ramsey Numbers by Partitioning Colored Graphs.
Journal Of Graph Theory
, 84
(4)
pp. 477-500.
10.1002/jgt.22036.
Preview |
Text
RamseyFinal.pdf - Accepted Version Download (320kB) | Preview |
Abstract
In this paper we prove a new result about partitioning coloured complete graphs and use it to determine certain Ramsey Numbers exactly. The partitioning theorem we prove is that for k ≥ 1, in every edge colouring of Kn with the colours red and blue, it is possible to cover all the vertices with k disjoint red paths and a disjoint blue balanced complete (k+1)-partite graph. When the colouring of Kn is connected in red, we prove a stronger result—that it is possible to cover all the vertices with k red paths and a blue balanced complete (k + 2)-partite graph. Using these results we determine the Ramsey Number of a path, Pn, versus a balanced complete t-partite graph on tm vertices, Kt m, whenever m ≡ 1 (mod n−1). We show that in this case R(Pn, Kt m) = (t − 1)(n − 1) + t(m − 1) + 1, generalizing a result of Erd˝os who proved the m = 1 case of this result. We also determine the Ramsey Number of a path Pn versus the power of a path P t n . We show that R(Pn, Pt n ) = t(n − 1) + j n t+1 k , solving a conjecture of Allen, Brightwell, and Skokan.
Type: | Article |
---|---|
Title: | Calculating Ramsey Numbers by Partitioning Colored Graphs |
Open access status: | An open access version is available from UCL Discovery |
DOI: | 10.1002/jgt.22036 |
Publisher version: | https://doi.org/10.1002/jgt.22036 |
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. |
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/10112659 |
Archive Staff Only
View Item |