Rainbow independent sets in certain classes of graphs
Rainbow independent sets in certain classes of graphs
复制标题
某些类图中的彩虹独立集
DOI：
10.1002/jgt.22989
复制
发表时间：
2019
影响因子：
0.9
通讯作者：
Minki Kim
中科院分区：
文献类型：
--
作者：
R. Aharoni;Joseph Briggs;Jinha Kim;Minki Kim
图和超图中的彩虹匹配已经被广泛研究，其中一个动机来自于三部超图中的匹配问题，包括拉丁方中的横截问题。图中的匹配是线图中的独立集，因此一个自然的问题是将研究扩展到一般图中的彩虹独立集。我们研究以下形式的问题：给定一类图C ${\mathscr{C}}$，在属于C ${\mathscr{C}}$的图中需要多少个大小为n $n$的独立集来保证大小为m $m$的彩虹集的存在？一个特别有趣的情况是一类图有一个给定的上限，其最大程度。
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 C ${\mathscr{C}}$ of graphs, how many independent sets of size n $n$ in a graph belonging to C ${\mathscr{C}}$ are needed to guarantee the existence of a rainbow set of size m $m$ ? A particularly interesting case is the class of graphs having a given upper bound on their maximum degree.