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 $43\le R(5, 5)\le 48$ and conjectured that R ( 5, 5 ) = 43 $R(5, 5)=43$ . If 44 ≤ R ( 5, 5 ) ≤ 48 $44\le R(5, 5)\le 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})$ .