{"id":"arxiv/2609.34898","url":"https://arxiv.org/abs/2609.34898","tags":["math.CO"],"score":0,"title":"On rainbow saturated graphs with minimum number of edges","domain":"math.CO","source":"arxiv","authors":["Yanzhe Qiu","Mei Lu","Yilin Pan","Yiduo Xu"],"reviews":0,"subject":"math.CO","summary":"Let $F$ be a fixed graph without isolated vertices. An edge-colored graph is $F$-rainbow saturated if it contains no rainbow copy of $F$, but the addition of any missing edge in any color creates a rainbow copy of $F$. The rainbow saturation number $rsat(n,F)$ is the minimum number of edges in such a graph on $n$ vertices. We prove a dichotomy governed by isolated edges: if $F$ contains an isolated edge, then $rsat(n,F)=O(1)$ for all sufficiently large $n$, while if $F$ has no isolated edge, then $rsat(n,F)=Θ(n)$. The linear lower bound is expressed in terms of a directed weight parameter…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-28","reactions":{}}