2024/03/22 by Halfpap, Anastasia, Lidický, Bernard, Masařík, Tomáš
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2403.15602
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).