Weak rainbow saturation numbers of graphs

From the introduction: ``A famous Turán problem asks, for a fixed graph \(H\), what is the maximum number of edges in an \(H\)-free graph on \(n\) vertices. For a fixed graph \(H\), a graph \(G\) is called \(H\)-saturated if \(G\) is \(H\)-free but adding any nonedge to \(G\) creates a copy of \(H\). The saturation number \(\operatorname{sat}(n,H)\) is the smallest number of edges in an \(H\)-saturated graph on \(n\) vertices.\N\N\textit{A. A. Zykov} initiated this number in [Mat. Sb., Nov. Ser. 24(66), 163--188 (1949; Zbl 0033.02602)]. \N\NA graph \(G\) is called weakly \(H\)-saturated if there exists an ordering \(e_1 e_2,\dots, e_m\) of the nonedges of \(G\) such that for each \(i\in [m]\), the graph \(G_i := G + \{e_1,\dots ,e_i\}\) contains a copy of \(H\) containing \(e_i\) as an edge. The weak saturation number \(\operatorname{wsat}(n,H)\) is the smallest number of edges in a weakly \(H\)-saturated graph on \(n\) vertices.\N\NFor a fixed graph \(H\), we say that an edge-colored graph \(G\) is \(H\)-rainbow saturated if \(G\) does not contain a rainbow copy of \(H\), but the addition of any non-edge in any color from \(\mathbb{N}\) creates a rainbow copy of \(H\). \textit{A. Girão} et al. [J. Graph Theory 94, No. 3, 421--444 (2020; Zbl 1485.05060)] defined the rainbow saturation number of \(H\), denoted by \(\operatorname{rsat}(n,H)\), to be the minimum number of edges in an \(H\)-rainbow saturated graph on \(n\) vertices and \Nconjectured that the rainbow saturation number of any nonempty graph is at most linear in \(n\).\N\N\textit{N. Behague} et al. [SIAM J. Discrete Math. 38, No. 2, 1239--1249 (2024; Zbl 1536.05170)] defined the weak rainbow saturation number of \(H\), denoted by \(\operatorname{rwsat}(n,H)\) to be the minimum number of edges in a weakly \(H\)-rainbow saturated graph on \(n\) vertices \Nand posed the following question. For any nonempty graph \(H\), does the limit \(\operatorname{rwsat}(n,H)/n\) exist as \(n\) goes to infinity? \N\NIn this paper, the authors fully resolve this problem by proving that such a limit exists for any nonempty graph \(H\). They also raise some open problems for further research.

Cites work

This page was built for publication: Weak rainbow saturation numbers of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6988427)