Calculating Ramsey Numbers by Partitioning Colored Graphs

In this article we prove a new result about partitioning colored complete graphs and use it to determine certain Ramsey numbers exactly. The partitioning theorem we prove is that for k >= 1, in every edge coloring of K-n with the colors 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 coloring of K-n 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 an n-vertex path, P-n, versus a balanced complete t-partite graph ontm vertices, K-m(t), whenever m = 1 (mod n - 1). We show that in this case R(P-n, K-m(t)) = (t - 1)(n - 1) + t (m - 1) + 1, generalizing a result of Erdos who proved the m = 1 case of this result. We also determine the Ramsey number of a path P-n versus the power of a path P-n(t). We show that R(P-n, P-n(t)) = t (n - 1) + [n/t+1], solving a conjecture of Allen, Brightwell, and Skokan. (C) 2016 Wiley Periodicals, Inc.