Gallai–Ramsey number for K5 ${K}_{5}$. Issue 3 (15th April 2022)

• Record Type: Journal Article
• Authors: Magnant, Colton; Schiermeyer, Ingo
• Is Part Of: Journal of graph theory. Volume 101:Issue 3(2022)
• Page Start: 455
• Page End: 492
• Publication Date: 2022-04-15
• Subjects: complete graphs -- Gallai–Ramsey -- Ramsey number; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22835
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: Given a graph H $H$, the k $k$ ‐colored Gallai–Ramsey number g r k ( K 3 : H ) $g{r}_{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 ) $g{r}_{k}({K}_{3}:{K}_{5})$ .