Ramsey goodness of complete multipartite graphs with one large part

Abstract

For graph $G$, a connected graph $H$ of order $n$ is $G$-good if $r(G,H)=(\ddot{I}‡(G)-1)(n-1)+s(G)$, where $\ddot{I}‡(G)$ is the chromatic number of $G$ and $s(G)$ is the minimum size of a color class in a $\ddot{I}‡(G)$-coloring of $G$. Let $K_{\hat{I}{\pm }_1,\dots ,\hat{I}{\pm }_p,n}$ be the complete $(p+1)$-partite graph with partite sets of sizes $\hat{I}{\pm }_1,\dots ,\hat{I}{\pm }_p,n$. Burr, Faudree, Rousseau and Schelp (1983) showed that $K_{\hat{I}{\pm }_1,\dots ,\hat{I}{\pm }_p,n}$ are $(K_2+m{K}_1)$-good for large $n$. We determine graphs $G$ such that $K_{\hat{I}{\pm }_1,\dots ,\hat{I}{\pm }_p,n}$ are $G$-good for large $n$. The characterization depends on $\mathrm{snd}(\hat{I}{\pm }_i)$, the smallest non-divisor of $\hat{I}{\pm }_i$, where $1\le i\le p$.