Rainbow independent sets in certain classes of graphs


الملخص بالإنكليزية

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.

تحميل البحث