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 (Formula presented.) of graphs, how many independent sets of size (Formula presented.) in a graph belonging to (Formula presented.) are needed to guarantee the existence of a rainbow set of size (Formula presented.) ? A particularly interesting case is the class of graphs having a given upper bound on their maximum degree. © 2023 Wiley Periodicals LLC.