Induced Ramsey Number for a Star Versus a Fixed Graph

Abstract

We write $F{\buildrel {\text{ind}} \over \longrightarrow}(H,G)$ for graphs $F, G,$ and $H$, if for any coloring of the edges of $F$ in red and blue, there is either a red induced copy of $H$ or a blue induced copy of $G$. For graphs $G$ and $H$, let $\mathrm{IR}(H,G)$ be the smallest number of vertices in a graph $F$ such that $F{\buildrel {\text{ind}} \over \longrightarrow}(H,G)$.

In this note we consider the case when $G$ is a star on $n$ edges, for large $n$ and $H$ is a fixed graph. We prove that  $$ (\chi(H)-1) n \leq \mathrm{IR}(H, K_{1,n}) \leq (\chi(H)-1)^2n + \epsilon n,$$ for any $\epsilon>0$,  sufficiently large $n$, and $\chi(H)$ denoting the chromatic number of $H$. The lower bound is asymptotically tight  for any fixed bipartite $H$. The upper bound is attained up to a constant factor, for example when $H$ is a clique.