Stability and Ramsey numbers for cycles and wheels

作者：Sanhueza Matamala Nicolas^*

来源：Discrete Mathematics, 2016, 339(5): 1557-1565.

DOI：10.1016/j.disc.2015.12.031

• Ramsey theory
• Cycles
• Wheels
• Edge colorings
• Stability

We study the structure of red blue edge colorings of complete graphs, with no copies of the n-cycle C-n in red, and no copies of the m-wheel W-m = Cm * K-1 in blue. Our first result is that, if we take n = m and n odd, in any such coloring, one can delete at most two vertices to obtain a graph with a vertex-partition into three sets such that the edges inside the partition classes are red, and edges between partition classes are blue. As a second result, we obtain bounds for the Ramsey numbers r(C2k+1, W-2j) for k < j, which asymptotically confirm the values of 4j + 1, as conjectured by Zhang, Zhang and Chen.

• 出版日期2016-5-6