彩虹子集 Patial transversal

问题描述：给定图类 \(\mathcal{G}\)，图性质 \(\mathbb{P}\) 和正整数 \(s,t\)，确定一个最小的整数 \(N\)，使得对于图类 \(\mathcal{G}\) 中的任意一个图 \(G\) 的任意 \(N\) 个满足性质 \(\mathbb{P}\) 的 \(s\)-元集合构成的集族 \(\mathcal{F}\)，总可以在该集族中的集合中取出 \(t\) 个元素（每个集合至多取一个元素）它们构成的子集 \(T\) 在有性质 \(\mathbb{P}\). 上述要确定的正整数记为 \(f_{\mathcal{G}}(s,t)\).

• 若 \(\mathbb{P}\) 是 \(\Delta=0\)，则对应的问题称为是彩虹独立集问题.
• 若 \(\mathbb{P}\) 是 \(\Delta\leqslant k\)，i.e.，子集导出子图的最大度不超过 \(k\)，是否可以给出一些一般的结论呢？

考虑特殊的图类：圈图 \(C_n\)

• 猜想当 \(n\geqslant 2s+1\) 时有 \(f_{C_{n}}(s,s-1)=s\).
• 陆玫老师等证明了当 \(n=2s+1\) 时猜想成立，即 \(f_{C_{2s+1}}(s,s-1)=s\).
• 侯新民老师等证明了当 \(n> s^2\) 时猜想成立.