论文标题
彩虹独立的图表上
Rainbow independent sets on dense graph classes
论文作者
论文摘要
鉴于一个家庭$ \ MATHCAL {I} $在图中的独立集，彩虹独立集是独立集合$ i $，因此有一个注入$ ϕ \ colon i \ to \ mathcal {i} $，每个$ v \ in i $ $ $ v $均包含在$ ϕ（v）$中。 Aharoni，Briggs，J。Kim和M. Kim [某些类别的彩虹独立集。 Arxiv：1909.13143]确定了各种图类$ \ Mathcal {C} $是否$ \ Mathcal {C} $是否满足每个$ n $的属性，$ n = n = n = n（\ nathcal {c}，n）$ n $ n $ n $ n $ n y Mather in a $ n $ n y Mather in a $ n y Mather in a $ n y Mather in carcal in a $ n y Mather in carcal in a $ n y Mather in cagal Indercy in cagl Indercan c $ n y Mather in capal in cagal in a $ n n $} $ n $。在本文中，我们添加了满足此属性的两个密集的图形类，即，有限的邻域多样性的图和$ r $ $ $ $ $ $ $ $ $ r $的图表中的图中的图中的图表中的图表中的图表中的类别是有限的扩展类中的。
Given a family $\mathcal{I}$ of independent sets in a graph, a rainbow independent set is an independent set $I$ such that there is an injection $ϕ\colon I\to \mathcal{I}$ where for each $v\in I$, $v$ is contained in $ϕ(v)$. Aharoni, Briggs, J. Kim, and M. Kim [Rainbow independent sets in certain classes of graphs. arXiv:1909.13143] determined for various graph classes $\mathcal{C}$ whether $\mathcal{C}$ satisfies a property that for every $n$, there exists $N=N(\mathcal{C},n)$ such that every family of $N$ independent sets of size $n$ in a graph in $\mathcal{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.
