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 on t m 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 Erdős 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.