Premium
Calculating Ramsey Numbers by Partitioning Colored Graphs
Author(s) -
Pokrovskiy Alexey
Publication year - 2017
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22036
Subject(s) - combinatorics , mathematics , disjoint sets , conjecture , ramsey's theorem , edge coloring , colored , fractional coloring , discrete mathematics , graph , graph power , line graph , materials science , composite material
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.