Ramsey numbers and Gallai--Ramsey numbers of disjoint unions of cherries

Abstract

For graphs $G_1,\dots ,G_k$, the Ramsey number $R(G_1,\dots ,G_k)$ is the smallest positive integer $N$ such that every $k$-edge-coloring of $K_N$ contains a monochromatic copy of $G_i$ in color $i$ for some $i\in [k]$. The Gallai--Ramsey number $GR(G_1,\dots ,G_k)$ is defined analogously, with the colorings restricted to Gallai colorings (i.e., edge-colorings with no rainbow triangle). A copy of $P_3$ is called a cherry. Let $n_i{P}_3$ denote the disjoint union of $n_i$ cherries. Wu, Magnant, Nowbandegani, and Xia (Discrete Appl. Math., 2019) proposed two conjectures: \[ R(n_1P_3,\ldots,n_kP_3)=N\ \text{and}\ GR(n_1P_3,\ldots,n_kP_3)=N\,, \] where $N=2\max \{n_1,\dots ,n_k\}+{\sum }_{i=1}^k{n}_i-k+1$. We disprove the Ramsey conjecture and provide some sufficient conditions for determining the exact value of $R(n_1{P}_3,\dots ,n_k{P}_3)$. In contrast, we confirm the Gallai--Ramsey conjecture.