2017/09/18 by Christian Bosse, Zi‐Xia Song, Bosse, Christian +1
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Advanced Topology and Set Theory #Advanced Graph Theory Research
paper · pdf · doi:10.48550/arxiv.1709.06130
We study Ramsey-type problems in Gallai-colorings. Given a graph G and an integer k≥1, the Gallai-Ramsey number grk(K3,G) is the least positive integer n such that every k-coloring of the edges of the complete graph on n vertices contains either a rainbow triangle or a monochromatic copy of G. It turns out that grk(K3, G) behaves more nicely than the classical Ramsey number rk(G). However, finding exact values of grk (K3, G) is far from trivial. In this paper, we prove that grk(K3, C9)= 4⋅ 2k+1 for all k≥1. This new result provides partial evidence for the first open case of the Triple Odd Cycle Conjecture of Bondy and Erdős from 1973. Our technique relies heavily on the structural result of Gallai on edge-colorings of complete graphs without rainbow triangles. We believe the method we developed can be used to determine the exact values of grk(K3, Cn) for odd integers n≥11.