Contents Online

# Journal of Combinatorics

## Volume 11 (2020)

### Number 4

### On edge-colored saturation problems

Pages: 639 – 655

DOI: https://dx.doi.org/10.4310/JOC.2020.v11.n4.a4

#### Authors

#### Abstract

Let $\mathcal{C}$ be a family of edge-colored graphs. A $t$-edge colored graph $G$ is $(\mathcal{C}, t)$-saturated if $G$ does not contain any graph in $\mathcal{C}$ but the addition of any edge in any color in $[t]$ creates a copy of some graph in $\mathcal{C}$. Similarly to classical saturation functions, define $\operatorname{sat}_t (n, \mathcal{C})$ to be the minimum number of edges in a $(\mathcal{C}, t)$ saturated graph. Let $\mathcal{C}_r (H)$ be the family consisting of every edge-colored copy of $H$ which uses exactly $r$ colors.

In this paper we consider a variety of colored saturation problems. We determine the order of magnitude for $\operatorname{sat}_t (n, \mathcal{C}_r (K_k))$ for all $r$, showing a sharp change in behavior when $r \geq \binom{k-1}{2} + 2$. A particular case of this theorem proves a conjecture of Barrus, Ferrara, Vandenbussche, and Wenger. We determine $\operatorname{sat}_t (n, \mathcal{C}_2 (K_3))$ exactly and determine the extremal graphs. Additionally, we document some interesting irregularities in the colored saturation function.

#### Keywords

saturation, edge-coloring

Received 3 December 2017

Accepted 9 August 2019

Published 9 October 2020