论文标题
彩虹饱和数是线性的
The rainbow saturation number is linear
论文作者
论文摘要
给定图表$ h $，我们说如果不包含$ h $的彩虹副本，则是$ h $ rainbow饱和的$ g $，但是任何颜色的任何非边缘都会产生$ h $的彩虹副本。彩虹饱和数$ \ text {rsat}（n，h）$是所有$ h $ rainbow饱和的边缘颜色图中的最小边数。我们证明，对于任何非空图$ h $，彩虹饱和数字在$ n $中是线性的，因此证明了Girão，Lewis和Popielarz的猜想。此外，我们还提供了完整图的彩虹饱和数量的上限，这是Girão，Lewis和Popielarz的第二个猜想。
Given a graph $H$, we say that an edge-coloured graph $G$ is $H$-rainbow saturated if it does not contain a rainbow copy of $H$, but the addition of any non-edge in any colour creates a rainbow copy of $H$. The rainbow saturation number $\text{rsat}(n,H)$ is the minimum number of edges among all $H$-rainbow saturated edge-coloured graphs on $n$ vertices. We prove that for any non-empty graph $H$, the rainbow saturation number is linear in $n$, thus proving a conjecture of Girão, Lewis, and Popielarz. In addition, we also give an improved upper bound on the rainbow saturation number of the complete graph, disproving a second conjecture of Girão, Lewis, and Popielarz.
