Rainbow independent sets in certain classes of graphs
Minki Kim (Technion)
Tuesday, April 30, 2019, 13:00 – 14:00, -101
Let $F = (F_1, \ldots, F_m)$ be a collection of (not neccessarily distinct) sets. A (partial) rainbow set for $F$ is a set of the form $R = {x_{i_1}, \ldots, x_{i_k}}$ of distinct elements, where $1 \leq i_1 < \cdots < i_k \leq m$ and $x_{i_j}$ is an element of $F_{i_j}$. We are interested in the following question: given sufficiently many independent sets of size $a$ in a graph belonging to a certain class, there exists a rainbow independent set of size $b$. In this talk, I will present our recent results on this question, mainly regarding $H$-(induced) free graphs and graphs of bounded maximum degree. This is joint work with Ron Aharoni, Joseph Briggs and Jinha Kim.