Gallai-Ramsey number of odd cycles with chords

Abstract

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\ge 1$, the Gallai-Ramsey number $G{R}_k(H)$ of a given graph $H$ is the least positive integer $N$ such that every Gallai $k$-coloring of the complete graph $K_N$ contains a monochromatic copy of $H$. Let $C_m$ denote the cycle on $m\ge 4$ vertices and let ${\Theta }_m$ denote the family of graphs obtained from $C_m$ by adding an additional edge joining two non-consecutive vertices. We prove that $G{R}_k({\Theta }_{2n+1})=n\cdot 2^k+1$ for all $k\ge 1$ and $n\ge 3$. This implies that $G{R}_k(C_{2n+1})=n\cdot 2^k+1$ all $k\ge 1$ and $n\ge 3$. Our result yields a unified proof for the Gallai-Ramsey number of all odd cycles on at least five vertices.