A conjecture on Gallai-Ramsey numbers of even cycles and paths
A conjecture on Gallai-Ramsey numbers of even cycles and paths
复制标题
DOI：
--
复制
发表时间：
2018-03
期刊：
影响因子：
--
通讯作者：
Zi-Xia Song;Jingmei Zhang
中科院分区：
文献类型：
--
作者：
Zi-Xia Song;Jingmei Zhang
Gallai 着色是对没有彩虹三角形的完整图的边缘进行着色，Gallai $k$ 着色是使用 $k$ 颜色的 Gallai 着色。给定一个整数 $k\ge1$ 和图 $H_1, H_2, \ldots, H_k$，Gallai-Ramsey 数 $GR(H_1, H_2, \ldots, H_k)$ 是最小整数 $n$，使得完整图 $K_n$ 的每个加莱 $k$ 着色都包含 $H_i$ 的单色副本，颜色为 $i$，对于某些 $i \in \{1,2, \ldots, k\}$。当$H = H_1 = \cdots = H_k$时，我们只需写$GR_k(H)$。我们研究偶数周期和路径的加莱拉姆齐数。对于所有 $n\ge3$ 和 $k\ge1$，令 $G_i=P_{2i+3}$ 为所有 $i\in\{0,1, \ldots, n-2\}$ 和 $G_{n-1}\in\{C_{2n}, P_{2n+1}\}$ 在 $2i+3$ 顶点上的路径。让 $ i_j\in\{0,1,\ldots, n-1 \}$ 对于所有 $j\in\{1,2, \ldots, k\}$ 和 $ i_1\ge i_2\ge\cdots\ge i_k $。第一作者最近推测 $GR(G_{i_1}, G_{i_2}, \ldots, G_{i_k}) = 3+\min\{i_1,n^*-2\}+\sum_{j=1}^k i_j$，其中 $n^* =n$ 当 $G_{i_1}\ne 时 当 $G_{i_1}= P_{2n+1}$ 时，P_{2n+1}$ 和 $n^* =n+1$。这个猜想的真实性意味着，对于所有 $n\ge3$ 和 $k\ge1$，$GR_k(C_{2n})=GR_k(P_{2n})=(n-1)k+n+1$，对于所有 $n\ge1$ 和 $k\ge1$，$GR_k(P_{2n+1})=(n-1)k+n+2$。在本文中，我们证明上述猜想对于$n\in\{3,4\}$和所有$k\ge1$成立。我们的证明仅依赖于加莱的结果和经典拉姆齐数 $R(H_1, H_2)$，其中 $H_1, H_2\in\{C_8, C_6, P_7, P_5, P_3\}$。我们相信我们在这里开发的重新着色方法对于解决后续案例，甚至猜想将非常有用。
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\ge1$ and graphs $H_1, H_2, \ldots, H_k$, the Gallai-Ramsey number $GR(H_1, H_2, \ldots, 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,2, \ldots, k\}$. When $H = H_1 = \cdots = H_k$, we simply write $GR_k(H)$. We study Gallai-Ramsey numbers of even cycles and paths. For all $n\ge3$ and $k\ge1$, let $G_i=P_{2i+3}$ be a path on $2i+3$ vertices for all $i\in\{0,1, \ldots, n-2\}$ and $G_{n-1}\in\{C_{2n}, P_{2n+1}\}$. Let $ i_j\in\{0,1,\ldots, n-1 \}$ for all $j\in\{1,2, \ldots, k\}$ with $ i_1\ge i_2\ge\cdots\ge i_k $. The first author recently conjectured that $ GR(G_{i_1}, G_{i_2}, \ldots, G_{i_k}) = 3+\min\{i_1,n^*-2\}+\sum_{j=1}^k i_j$, where $n^* =n$ when $G_{i_1}\ne P_{2n+1}$ and $n^* =n+1$ when $G_{i_1}= P_{2n+1}$. The truth of this conjecture implies that $GR_k(C_{2n})=GR_k(P_{2n})=(n-1)k+n+1$ for all $n\ge3$ and $k\ge1$, and $GR_k(P_{2n+1})=(n-1)k+n+2$ for all $n\ge1$ and $k\ge1$. In this paper, we prove that the aforementioned conjecture holds for $n\in\{3,4\}$ and all $k\ge1$. Our proof relies only on Gallai's result and the classical Ramsey numbers $R(H_1, H_2)$, where $H_1, H_2\in\{C_8, C_6, P_7, P_5, P_3\}$. We believe the recoloring method we developed here will be very useful for solving subsequent cases, and perhaps the conjecture.