论文标题
完整图的彩虹饱和度
Rainbow saturation for complete graphs
论文作者
论文摘要
如果其所有边缘都会收到不同的颜色，我们将其称为边彩色彩虹。如果$γ$不包含$ h $的彩虹副本，并且将任何颜色的边缘添加到$γ$的情况下会产生$ h $的彩虹副本，则一个边缘色的图$γ$被称为$ h $ rainbow饱和。彩虹饱和数$ sat（n，{r}（h））$是$ n $ vertex $ h $ h $ rainbow饱和图中的最小边数。 Girão，Lewis和Popielarz猜想$ sat（n，{r}（k_r））= 2（r-2）n+o（1）$（固定$ r \ geq 3 $）。关于这种猜想的反驳，我们确定在每$ r \ geq 3 $中都存在一个常数$α_r$，以至于$ r + om +ω\ left（r^{1/3} \ right）\ leα_r\ leα_r\ le r + r + r + r + r^{1/2} {1/2} \ qquad \ qquad \ qquad \ qquad \ qquad \ quad \ quad \ quad {and） n + o（1）。他们还引入了弱彩虹饱和数，并询问这是否等于$ k_r $的彩虹饱和数，因为完整图的标准弱饱和数等于标准饱和数。令人惊讶的是，我们的下限将彩虹饱和数与弱彩虹饱和数字分开，以负面回答这个问题。常数$α_r$的存在在肯定中解决了另一个问题，以获得完整的图表。此外，我们表明，如果我们有一个额外的假设，即边缘颜色$ k_r $ -rainbow饱和图必须是彩虹，那么Girão，Lewis和Popielarz的猜想是正确的。作为证明的成分，我们研究了$ k_r $饱和的图形，相对于删除一个边缘并添加两个边缘的操作而言。
We call an edge-colored graph rainbow if all of its edges receive distinct colors. An edge-colored graph $Γ$ is called $H$-rainbow saturated if $Γ$ does not contain a rainbow copy of $H$ and adding an edge of any color to $Γ$ creates a rainbow copy of $H$. The rainbow saturation number $sat(n,{R}(H))$ is the minimum number of edges in an $n$-vertex $H$-rainbow saturated graph. Girão, Lewis, and Popielarz conjectured that $sat(n,{R}(K_r))=2(r-2)n+O(1)$ for fixed $r\geq 3$. Disproving this conjecture, we establish that for every $r\geq 3$, there exists a constant $α_r$ such that $$r + Ω\left(r^{1/3}\right) \le α_r \le r + r^{1/2} \qquad \text{and} \qquad sat(n,{R}(K_r)) = α_r n + O(1).$$ Recently, Behague, Johnston, Letzter, Morrison, and Ogden independently gave a slightly weaker upper bound which was sufficient to disprove the conjecture. They also introduced the weak rainbow saturation number, and asked whether this is equal to the rainbow saturation number of $K_r$, since the standard weak saturation number of complete graphs equals the standard saturation number. Surprisingly, our lower bound separates the rainbow saturation number from the weak rainbow saturation number, answering this question in the negative. The existence of the constant $α_r$ resolves another of their questions in the affirmative for complete graphs. Furthermore, we show that the conjecture of Girão, Lewis, and Popielarz is true if we have an additional assumption that the edge-colored $K_r$-rainbow saturated graph must be rainbow. As an ingredient of the proof, we study graphs which are $K_r$-saturated with respect to the operation of deleting one edge and adding two edges.
