Gallai–Ramsey number for K5 K_5. Issue 3 (15th April 2022) - Magnant, Colton; Schiermeyer, Ingo
Abstract: Given a graph H H, the k k ‐colored Gallai–Ramsey number g r k ( K 3 : H ) gr_k(K_3:H) is defined to be the minimum integer n n such that every k k ‐coloring of the edges of the complete graph on n n vertices contains either a rainbow triangle or a monochromatic copy of H . H. Fox et al. conjectured the values of the Gallai–Ramsey numbers for complete graphs. Recently, this conjecture has been verified for the first open case, when H = K 4 H=K_4 . In this paper we attack the next case, when H = K 5 H=K_5 . Surprisingly it turns out, that the validity of the conjecture depends upon the (yet unknown) value of the Ramsey number R ( 5, 5 ) R(5, 5) . It is known that 43 ≤ R ( 5, 5 ) ≤ 48 43R(5, 5)48 and conjectured that R ( 5, 5 ) = 43 R(5, 5)=43 . If 44 ≤ R ( 5, 5 ) ≤ 48 44R(5, 5)48, then Fox et al.'s conjecture is true and we present a complete proof. If, however, R ( 5, 5 ) = 43 R(5, 5)=43, then Fox et al.'s conjecture is false, meaning that exactly one of these conjectures is true while the other is false. For the case when R ( 5, 5 ) = 43 R(5, 5)=43, we show lower and upper bounds for the Gallai–Ramsey number g r k ( K 3 : K 5 ) gr_k(K_3:K_5) .