2018/08/29 by Christian Bosse, Zi‐Xia Song, Bosse, Christian +3
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.1808.09963
openalex publication_date 2018/08/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A Gallai coloring of a complete graph is an edge-coloring such that no triangle has all its edges colored differently. A Gallai k-coloring is a Gallai coloring that uses k colors. Given an integer k≥1 and a graph H, the Gallai-Ramsey number GRk(H) is the least positive integer n such that every Gallai k-coloring of the complete graph Kn contains a monochromatic copy of H. Gyárfás, Sárközy, Sebő and Selkow proved in 2010 that GRk (H) is exponential in k if H is not bipartite, linear in k if H is bipartite but not a star, and constant (does not depend on k) when H is a star. Hence, GRk(H) is more well-behaved than the classical Ramsey number Rk(H). However, finding exact values of GRk (H) is far from trivial, even when |V(H)| is small. In this paper, we first improve the existing upper bounds for Gallai-Ramsey numbers of odd cycles by showing that GRk(C2n+1) ≤ (nln n) ⋅ 2k -(k+1)n+1 for all k ≥ 3 and n ≥ 8. We then prove that GRk( C13)= 6⋅ 2k+1 and GRk( C15)= 7⋅ 2k+1 for all k≥1.