Proper Rainbow Saturation Numbers for Cycles
Date
2024-03-26
Authors
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
We say that an edge-coloring of a graph G is proper if every pair of incident edges receive distinct colors, and is rainbow if no two edges of G receive the same color. Furthermore, given a fixed graph F, we say that G is rainbow F-saturated if G admits a proper edge-coloring which does not contain any rainbow subgraph isomorphic to F, but the addition of any edge to G makes such an edge-coloring impossible. The maximum number of edges in a rainbow F-saturated graph is the rainbow Turán number, whose study was initiated in 2007 by Keevash, Mubayi, Sudakov, and Verstraëte. Recently, Bushaw, Johnston, and Rombach introduced study of a corresponding saturation problem, asking for the minimum number of edges in a rainbow F-saturated graph. We term this minimum the proper rainbow saturation number of F, denoted sat∗(n,F). We asymptotically determine sat∗(n,C4), answering a question of Bushaw, Johnston, and Rombach. We also exhibit constructions which establish upper bounds for sat∗(n,C5) and sat∗(n,C6).
Series Number
Journal Issue
Is Version Of
Versions
Series
Academic or Administrative Unit
Type
Preprint
Comments
This preprint is made available from arXiv at doi:https://doi.org/10.48550/arXiv.2403.15602. This work is available under a Creative Commons Attribution 4.0 International License https://creativecommons.org/licenses/by/4.0/.