2018/09/01 by Zhang, Fangfang, Song, Zi-Xia, Chen, Yaojun
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1809.00227
A Gallai coloring is a coloring of the edges of a complete graph without rainbow triangles, and a Gallai k-coloring is a Gallai coloring that uses at most k colors. For an integer k≥ 1, the Gallai-Ramsey number GRk(H) of a given 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. 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. We prove that GRk(Θ2n+1)=n⋅ 2k+1 for all k≥ 1 and n≥ 3. This implies that GRk(C2n+1)=n⋅ 2k+1 all k≥ 1 and n≥ 3. Our result yields a unified proof for the Gallai-Ramsey number of all odd cycles on at least five vertices.