Rainbow independent sets in certain classes of graphs
Ron Aharoni, Joseph Briggs, Jinha Kim, Minki Kim · Journal of Graph Theory · 2023
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 of graphs, how many independent sets of size in a graph belonging to are needed to guarantee the existence of a rainbow set of size ? A particularly interesting case is the class of graphs having a given upper bound on their maximum degree.