Rainbow independent sets on dense graph classes

Abstract

© 2021 Elsevier B.V.Given a family I of independent sets in a graph, a rainbow independent set is an independent set I such that there is an injection ϕ:I→I where for each v∈I, v is contained in ϕ(v). Aharoni et al. (2019) determined for various graph classes C whether C satisfies a property that for every n, there exists N=N(C,n) such that every family of N independent sets of size n in a graph in C contains a rainbow independent set of size n. In this paper, we add two dense graph classes satisfying this property, namely, the class of graphs of bounded neighborhood diversity and the class of r-powers of graphs in a bounded expansion class.