Abstract | ||
---|---|---|
Abstract 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. |
Year | DOI | Venue |
---|---|---|
2022 | 10.1016/J.DAM.2021.04.007 | Discrete Applied Mathematics |
DocType | Volume | Citations |
Journal | 312 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jin-ha Kim | 1 | 329 | 18.78 |
Kim Minki | 2 | 0 | 0.34 |
Kwon O-joung | 3 | 0 | 0.34 |