2019/06/12 by Fangfang Zhang, Zi‐Xia Song, Zhang, Fangfang +3
Mathematics · #05C15 #05C55 #05D10 #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1906.05263
openalex publication_date 2019/06/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For a graph H and an integer k≥1, the k-color Ramsey number Rk(H) is the least integer N such that every k-coloring of the edges of the complete graph KN contains a monochromatic copy of H. Let Cm denote the cycle on m≥4 vertices and let Θm denote the family of graphs obtained from Cm by adding an additional edge joining two non-consecutive vertices. Unlike Ramsey number of odd cycles, little is known about the general behavior of Rk(C2n) except that Rk(C2n)≥ (n-1)k+n+k-1 for all k≥2 and n≥2. In this paper, we study Ramsey number of even cycles with chords under Gallai colorings, where a Gallai coloring is a coloring of the edges of a complete graph without rainbow triangles. For an integer k≥ 1, the Gallai-Ramsey number GRk(H) of a graph H is the least positive integer N such that every Gallai k-coloring of the complete graph KN contains a monochromatic copy of H. We prove that GRk(Θ2n)=(n-1)k+n+1 for all k≥ 2 and n≥ 3. This implies that GRk(C2n)=(n-1)k+n+1 all k≥ 2 and n≥ 3. Our result yields a unified proof for the Gallai-Ramsey number of all even cycles on at least four vertices.