pith. sign in

arxiv: 2409.15258 · v2 · pith:N7DORIB6new · submitted 2024-09-23 · 🧮 math.CO

On the proper rainbow saturation numbers of cliques, paths, and odd cycles

classification 🧮 math.CO
keywords rainbowpropergraphnumbersaturationtextdetermineedge-coloring
0
0 comments X
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.