Large stars with few colors

Abstract

A recent question in generalized Ramsey theory is that for fixed positive integers $s\le t$, at least how many vertices can be covered by the vertices of no more than $s$ monochromatic members of the family $\mathcal{F}$ in every edge coloring of $K_n$ with $t$ colors. This is related to an old problem of Chung and Liu: for graph $G$ and integers $1\le s<t$ what is the smallest positive integer $n=R_{s,t}(G)$ such that every coloring of the edges of $K_n$ with $t$ colors contains a copy of $G$ with at most $s$ colors. We answer this question when $G$ is a star and $s$ is either $t-1$ or $t-2$ generalizing the well-known result of Burr and Roberts.