2019/01/11 by Colton Magnant, Magnant, Colton, Ingo Schiermeyer +1
Mathematics · #05C55 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C55
paper · pdf · doi:10.48550/arxiv.1901.03622
38 pages, 4 tables, 1 figure
arxiv created 2019/01/11 · arxiv updated 2019/01/14
Given a graph H, the k-colored Gallai Ramsey number grk(K3 : H) is defined to be the minimum integer n such that every k-coloring of the edges of the complete graph on n vertices contains either a rainbow triangle or a monochromatic copy of H. Fox et al. [J. Fox, A. Grinshpun, and J. Pach. The Erd\H os-Hajnal conjecture for rainbow triangles. J. Combin. Theory Ser. B, 111:75-125, 2015.] conjectured the value of the Gallai Ramsey numbers for complete graphs. Recently, this conjecture has been verified for the first open case, when H = K4. In this paper we attack the next case, when H = K5. Surprisingly it turns out, that the validity of the conjecture depends upon the (yet unknown) value of the Ramsey number R(5,5). It is known that 43 ≤ R(5,5) ≤ 48 and conjectured that R(5,5)=43 [B.D. McKay and S.P. Radziszowski. Subgraph counting identities and Ramsey numbers. J. Combin. Theory Ser. B, 69:193-209, 1997]. If 44 ≤ R(5,5) ≤ 48, then Fox et al.'s conjecture is true and we present a complete proof. If, however, R(5,5)=43, then Fox et al.'s conjecture is false, meaning that at least one of these two conjectures must be false. For the case when R(5, 5) = 43, we show lower and upper bounds for the Gallai Ramsey number grk(K3 : K5).