Rainbow independent sets in certain classes of graphs

Abstract

Rainbow matchings in graphs and in hypergraphs have been studied extensively, one motivation coming from questions on matchings in 3-partite hypergraphs, including questions on transversals in Latin squares. Matchings in graphs are independent sets in line graphs, so a natural problem is to extend the study to rainbow independent sets in general graphs. We study problems of the following form: given a class C ${\mathscr{C}}$ of graphs, how many independent sets of size n $n$ in a graph belonging to C ${\mathscr{C}}$ are needed to guarantee the existence of a rainbow set of size m $m$? A particularly interesting case is the class of graphs having a given upper bound on their maximum degree.