Rainbow Independent Sets in Cycles

Abstract

For a given class $\mathcal{C}$ of graphs and given integers $m\le n$, let $f_{\mathcal{C}}(n,m)$ be the minimal number $k$ such that every $k$ independent $n$-sets in any graph belonging to $\mathcal{C}$ have a (possibly partial) rainbow independent $m$-set. In this paper, we consider the case $\mathcal{C}=\{C_{2s+1}\}$ and show that $f_{C_{2s+1}}(s,s)=s$. Our result is a special case of the conjecture (Conjecture 2.9) proposed by Aharoni et al in \cite{Aharoni}.