On the proper rainbow saturation numbers of cliques, paths, and odd cycles
classification
🧮 math.CO
keywords
rainbowpropergraphnumbersaturationtextdetermineedge-coloring
read the original abstract
Given a graph $H$, we say a graph $G$ is properly rainbow $H$-saturated if there is a proper edge-coloring of $G$ which contains no rainbow copy of $H$, but adding any edge to $G$ makes such an edge-coloring impossible. The proper rainbow saturation number, denoted $\text{sat}^*(n,H)$, is the minimum number of edges in an $n$-vertex rainbow $H$-saturated graph. We determine the proper rainbow saturation number for paths up to an additive constant and asymptotically determine $\text{sat}^*(n,K_4)$. In addition, we bound $\text{sat}^*(n,H)$ when $H$ is a larger clique, tree of diameter at least 4, or odd cycle.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.