Gallai-Ramsey numbers of $C_{10}$ and $C_{12}$

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 $k$ colors. Given an integer $k\ge 1$ and graphs $H_1,\dots ,H_k$, the Gallai-Ramsey number $GR(H_1,\dots ,H_k)$ is the least integer $n$ such that every Gallai $k$-coloring of the complete graph $K_n$ contains a monochromatic copy of $H_i$ in color $i$ for some $i\in \{1,\dots ,k\}$. When $H=H_1=\cdots =H_k$, we simply write $G{R}_k(H)$. We continue to study Gallai-Ramsey numbers of even cycles and paths. For all $n\ge 3$ and $k\ge 1$, let $G_i=P_{2i+3}$ be a path on $2i+3$ vertices for all $i\in \{0,1,\dots ,n-2\}$ and $G_{n-1}\in \{C_{2n},P_{2n+1}\}$. Let $i_j\in \{0,1,\dots ,n-1\}$ for all $j\in \{1,\dots ,k\}$ with $i_1\ge i_2\ge \cdots \ge i_k$. Song recently conjectured that $GR(G_{i_1},\dots ,G_{i_k})=3+\min \{i_1,n^{\ast }-2\}+{\sum }_{j=1}^k{i}_j$, where $n^{\ast }=n$ when $G_{i_1}\ne P_{2n+1}$ and $n^{\ast }=n+1$ when $G_{i_1}=P_{2n+1}$. This conjecture has been verified to be true for $n\in \{3,4\}$ and all $k\ge 1$. In this paper, we prove that the aforementioned conjecture holds for $n\in \{5,6\}$ and all $k\ge 1$. Our result implies that for all $k\ge 1$, $G{R}_k(C_{2n})=G{R}_k(P_{2n})=(n-1)k+n+1$ for $n\in \{5,6\}$ and $G{R}_k(P_{2n+1})=(n-1)k+n+2$ for $1\le n\le 6$.

arXiv admin note: text overlap with arXiv:1803.07963