For a given class $\mathcal{ C}$ of graphs and given integers $m \leq 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. Motivated by known results on the finiteness and actual value of $f_\mathcal{ C}(n,m)$ when $\mathcal{ C}$ is the class of line graphs of graphs, we study this function for various other classes.
Categories: math.CO