Premium
Rainbow saturation of graphs
Author(s) -
Girão António,
Lewis David,
Popielarz Kamil
Publication year - 2020
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22532
Subject(s) - rainbow , combinatorics , mathematics , discrete mathematics , 1 planar graph , conjecture , graph , chordal graph , physics , quantum mechanics
In this paper, we study the following problem proposed by Barrus, Ferrara, Vandenbussche, and Wenger. Given a graph H and an integer t , what is sat t ( n , R ( H ) ) , the minimum number of edges in a t ‐edge‐colored graph G on n vertices such that G does not contain a rainbow copy of H , but adding to G a new edge in any color from { 1 , 2 , … , t } creates a rainbow copy of H ? Here, we completely characterize the growth rates of sat t ( n , R ( H ) ) as a function of n , for any graph H belonging to a large class of connected graphs and for any t ≥ e ( H ) . This classification includes all connected graphs of minimum degree 2. In particular, we prove that sat t ( n , R ( K r ) ) = Θ ( n log n ) , for any r ≥ 3 and t ≥ r 2 , thus resolving a conjecture of Barrus, Ferrara, Vandenbussche, and Wenger. We also pose several new problems and conjectures.