On rainbow saturated graphs with minimum number of edges
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.34898
curl -X POST /api/v1/records/arxiv/2609.34898/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.34898/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'