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

Michael Ferrara (Department of Mathematical and Statistical Sciences, University of Colorado, Denver, Co., U.S.A.)

Daniel Johnston (Department of Mathematics and Statistics, Skidmore College, Saratoga Springs, New York, U.S.A.)

Sarah Loeb (Department of Mathematics and Computer Science, Hampden-Sydney College, Hampden-Sydney, Virginia, U.S.A.)

Florian Pfender (Department of Mathematical and Statistical Sciences, University of Colorado, Denver, Co., U.S.A.)

Alex Schulte (Iowa State University, Ames, Ia., U.S.A.)

Heather C. Smith (Department of Mathematics and Computer Science, Davidson College, Davidson, North Carolina, U.S.A.)

Eric Sullivan (Department of Mathematical and Statistical Sciences, University of Colorado, Denver, Co., U.S.A.)

Michael Tait (Department of Mathematics and Statistics, Villanova University, Villanova, Pennsylvania, U.S.A.)

Casey Tompkins (Department of Mathematics, Karlsruhe Institute of Technology, Karlsruhe, Germany)

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

Full Text (PDF format)

Received 3 December 2017

Accepted 9 August 2019

Published 9 October 2020