Rainbow Independent Sets in Cycles

Abstract: For a given class

c a l C

of graphs and given integers

m l e n

, let

f_{c a l C} (n, m)

be the minimal number

k

such that every

k

independent

n

-sets in any graph belonging to

c a l C

have a (possibly partial) rainbow independent

m

-set. In this paper, we consider the case

c a l C = C_{2 s + 1}

and show that

f_{C_{2 s + 1}} (s, s) = s

. Our result is a special case of the conjecture (Conjecture 2.9) proposed by Aharoni et al in cite{Aharoni}.

This page was built for publication: Rainbow Independent Sets in Cycles