循环图的真彩虹饱和度数研究

《Discrete Mathematics》：Proper rainbow saturation numbers for cycles

这篇综述系统介绍了图的（proper）彩虹（rainbow）饱和度问题，特别是针对循环（cycles）的研究。文章在已有彩虹Turán数研究基础上，重点探讨了真彩虹饱和度数 sat?(n, F)，给出了C4饱和度的渐进精确界以及C5和C6的构造上界，并与经典饱和度数 sat(n, F) 进行了对比。

　　

2. C₄的界

我们首先改进 sat^?(n, C₄) 的上界，给出了一个构造表明 sat^?(n, C₄) ≤ 11n/6 + O(1)。在阐述构造之前，我们先建立一些关于真彩虹C₄-饱和图的性质，这些性质将贯穿全文。我们从汇集一些基本观察的命题开始。

命题 2.1

令 G 为一个彩虹 C₄-饱和图。则以下性质成立：

1. 1.
   G 至多包含一个度为 1 的顶点；
2. 2.
   对于任意顶点 u, v ∈ V(G)，d(u, v) ≤ 3；
3. 3.
   对于任意顶点 u, v ∈ V(G)，|N(u) ∩ N(v)| < 4。

3. 更长循环的上界

我们展示了一些为 sat^?(n, C₅) 和 sat^?(n, C₆) 提供上界的构造。每个构造都包含一个小的支配顶点集 D，而 D 的补集本质上诱导出一个不相交团的并集。

构造 2

对于 n ≥ 8，令 G(n, C₅) 为定义如下的 n 个顶点的图：指定两个顶点 u, v 作为泛点。此外，在 V(G) \ {u, v} 中加入一个最大匹配。

观察到 G(n, C₅) 包含 2n - 3 条与泛点相关联的边，以及 ?(n-2)/2? 条不与泛点关联的边。

4. 结论

虽然我们确定了 sat^?(n, C₄) 的渐进精确度，并为 sat^?(n, C₅) 和 sat^?(n, C₆) 构建了上界，但要找到精确的界仍然是开放性问题。

问题 4.1

确定对于所有 k 的 sat^?(n, C_k)。

在上一节使用SAT求解器时，我们遇到了以下问题。一个肯定的答案将简化计算。

问题 4.2

令 G 和 H 为有限图。设 K 为所有使得存在一个使用所有 k 种颜色且避免彩虹 H 副本的 G 的真 k-边着色方案中的 k 值。K 是否为一个区间？