2020/07/08 by Zhao Wang, Yaping Mao, Wang, Zhao +7
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.2007.04895
openalex publication_date 2020/07/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For two graphs G,H and a positive integer k, the Gallai-Ramsey number grk(G,H) is defined as the minimum number of vertices n such that any k-edge-coloring of Kn contains either a rainbow (all different colored) copy of G or a monochromatic copy of H. If G and H are both complete graphs, then we call it Gallai-Ramsey function. Fox and Sudakov proved grk(Ks,Kt)≤ s4kt. Alon et al. showed that grk(Ks,Kt)≤ (2s3+4s2)kt. In this paper, we prove that grk(Ks,Kt)≤ 2kts3kt for t≥ 47. We also give better upper bounds for grk(G,H) when G,H are some special graphs. In this paper, we derive some lower bounds for Gallai-Ramsey functions and numbers by Lovász Local Lemma.