Rainbow saturation of graphs

Authors

Abstract: 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

o p e r a t o r n a m e {s a t}_{t} l e f t (n, m a t h f r a k R (H) i g h t)

, the minimum number of edges in a

t

-edge-coloured 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 colour from

1, 2, l d o t s, t

creates a rainbow copy of

H

? Here, we completely characterize the growth rates of

o p e r a t o r n a m e {s a t}_{t} l e f t (n, m a t h f r a k R (H) i g h t)

as a function of

n

, for any graph

H

belonging to a large class of connected graphs and for any

t g e q e (H)

. This classification includes all connected graphs of minimum degree

2

. In particular, we prove that

o p e r a t o r n a m e {s a t}_{t} l e f t (n, m a t h f r a k R (K_{r}) i g h t) = T h e t a (n l o g n)

, for any

r g e q 3

and

t g e q r c h o o s e 2

, thus resolving a conjecture of Barrus, Ferrara, Vandenbussche, and Wenger. We also pose several new problems and conjectures.

Recommendations

Cited in

(14)

This page was built for publication: Rainbow saturation of graphs