Improved bounds for proper rainbow saturation
Abstract
Given a graph H , we say that a graph G is properly rainbow H-saturated if: (1) There is a proper edge colouring of G containing no rainbow copy of H ; (2) For every e ∉ E ( G ) , every proper edge colouring of G + e contains a rainbow copy of H . The proper rainbow saturation number sa t ⁎ ( n , H ) ⁎ is the minimum number of edges in a properly rainbow H -saturated graph. In this paper we use connections to the classical saturation and semi-saturation numbers to provide new upper bounds on sa t ⁎ ( n , H ) ⁎ for general cliques, cycles, and complete bipartite graphs. We also provide a necessary and sufficient condition for a graph to have constant proper rainbow saturation number.
Fields of Study & Subjects
Limits and Structures in Graph Theory
Advanced Graph Theory Research
Graph Labeling and Dimension Problems
Publication details
- Journal / source
- Discrete Mathematics
- Volume
- 349
- Issue
- 6
- Pages
- 115001–115001
- Publication date
- 28 January 2026
- Language
- EN