On Ramsey numbers of complete graphs with dropped stars

Abstract

Let $r(G,H)$ be the smallest integer $N$ such that for any $2$-coloring (say, red and blue) of the edges of $K\_n$, $n⩾N$, there is either a red copy of $G$ or a blue copy of $H$. Let $K\_n-K\_1,s$ be the complete graph on $n$ vertices from which the edges of $K\_1,s$ are dropped. In this note we present exact values for $r(K\_m-K\_1,1,K\_n-K\_1,s)$ and new upper bounds for $r(K\_m,K\_n-K\_1,s)$ in numerous cases. We also present some results for the Ramsey number of Wheels versus $K\_n-K\_1,s$.

arXiv comment9 pages ; 1 table in Discrete Applied Mathematics, Elsevier, 2016