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.

Download activity - last month

Export as XMLCSVJSON

Download activity - last 12 months

Export as JSONCSVXML

Downloads by country - last 12 months

Export as JSONXMLCSV

Archive Staff Only

View Item