Weakened Gallai-Ramsey Numbers for Books

Abstract

For $1\le s<t$ and any graph $G$, the weakened Gallai-Ramsey number $g{r}_s^t(G)$ is defined to be the least $p\in \mathbb{N}$ such that every Gallai $t$-coloring of the edges of $K_p$ (i.e., a $t$-coloring that lacks rainbow triangles) contains a subgraph isomorphic to $G$ whose edges use at most $s$ of the colors. In the case of a book graph $B_n:=K_2+n{K}_1$, Jakhar and Moun determined the values $g{r}_2^3(B_3)=6$ and $g{r}_2^3(B_4)=7$. In this paper, we extend their results to $t>3$ colors, and we determine the values of $g{r}_2^3(B_n)$ for $5\le n\le 15$. General lower bounds for $g{r}_2^t(B_n)$ are also given.

32 pages, 10 figures