Multicolor Ramsey numbers on stars versus pat

Abstract

For given simple graphs $H_1,H_2,\dots ,H_c$, the multicolor Ramsey number $R(H_1,H_2,\dots ,H_c)$ is defined as the smallest positive integer $n$ such that for an arbitrary edge-decomposition $\{G_i{\}}_{i=1}^c$ of the complete graph $K_n$, at least one $G_i$ has a subgraph isomorphic to $H_i$. Let $m,n_1,n_2,\dots ,n_c$ be positive integers and $\Sigma ={\sum }_{i=1}^c(n_i-1)$. Some bounds and exact values of $R(K_{1,n_1},\dots ,K_{1,n_c},P_m)$ have been obtained in literature. Wang (Graphs Combin., 2020) conjectured that if $\Sigma \not\equiv 0(\mathrm{mod}m-1)$ and $\Sigma +1\ge (m-3{)}^2$, then $R(K_{1,n_1},\dots ,K_{1,n_c},P_m)=\Sigma +m-1.$ In this note, we give a new lower bound and some exact values of $R(K_{1,n_1},\dots ,K_{1,n_c},P_m)$ when $m\le \Sigma$, $\Sigma \equiv k(\mathrm{mod}m-1)$, and $2\le k\le m-2$. These results partially confirm Wang's conjecture.

6 pages