2018/03/21 by Zi‐Xia Song, Song, Zi-Xia, Jingmei Zhang +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1803.07963
openalex publication_date 2018/03/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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. Given an integer k≥1 and graphs H1, …, Hk, the Gallai-Ramsey number GR(H1, …, Hk) is the least integer n such that every Gallai k-coloring of the complete graph Kn contains a monochromatic copy of Hi in color i for some i ∈ \1,2, …, k\. When H = H1 = ⋯ = Hk, we simply write GRk(H). We study Gallai-Ramsey numbers of even cycles and paths. For all n≥3 and k≥2, let Gi=P2i+3 be a path on 2i+3 vertices for all i∈\0,1, …, n-2\ and Gn-1∈\C2n, P2n+1\. Let ij∈\0,1,…, n-1 \ for all j∈\1,2, …, k\ with i1≥ i2≥⋯≥ ik . The first author recently conjectured that GR(Gi1, Gi2, …, Gik) = |Gi1|+∑j=2k ij. The truth of this conjecture implies that GRk(C2n)=GRk(P2n)=(n-1)k+n+1 for all n≥3 and k≥1, and GRk(P2n+1)=(n-1)k+n+2 for all n≥1 and k≥1. In this paper, we prove that the aforementioned conjecture holds for n∈\3,4\ and all k≥2. Our proof relies only on Gallai's result and the classical Ramsey numbers R(H1, H2), where H1, H2∈\C8, C6, P7, P5, P3\. We believe the recoloring method we developed here will be very useful for solving subsequent cases, and perhaps the conjecture.