Weakened Gallai-Ramsey Numbers for Books

Abstract

For $1\le s<t$ and any graph $G$, the weakened Gallai-Ramsey number $gr^t_s(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+nK_1$, Jakhar and Moun determined the values $gr^3_2(B_3)=6$ and $gr^3_2(B_4)=7$. In this paper, we extend their results to $t>3$ colors, and we determine the values of $gr^3_2(B_n)$ for $5\le n\le 15$. General lower bounds for $gr^t_2(B_n)$ are also given.