Ramsey-minimal saturation numbers for matchings

Given a family of graphs FF, a graph GG is FF-saturated   if no element of FF is a subgraph of GG, but for any edge ee in G¯, some element of FF is a subgraph of G+eG+e. Let sat(n,F)sat(n,F) denote the minimum number of edges in an FF-saturated graph of order nn, which we refer to as the saturation number or saturation function   of FF. If F={F}F={F}, then we instead say that GG is FF-saturated   and write sat(n,F).For graphs G,H1,…,HkG,H1,…,Hk, we write that G→(H1,…,Hk)G→(H1,…,Hk) if every kk-coloring of E(G)E(G) contains a monochromatic copy of HiHi in color ii for some ii. A graph GG is (H1,…,Hk)(H1,…,Hk)-Ramsey-minimal   if G→(H1,…,Hk)G→(H1,…,Hk) but for any e∈Ge∈G, (G−e)⁄→(H1,…,Hk)(G−e)⁄→(H1,…,Hk). Let Rmin(H1,…,Hk) denote the family of (H1,…,Hk)(H1,…,Hk)-Ramsey-minimal graphs.In this paper, motivated in part by a conjecture of Hanson and Toft (1987), we prove that sat(n,Rmin(m1K2,…,mkK2))=3(m1+⋯+mk−k) for m1,…,mk≥1m1,…,mk≥1 and n>3(m1+…+mk−k)n>3(m1+…+mk−k), and we also characterize the saturated graphs of minimum size. The proof of this result uses a new technique, iterated recoloring  , which takes advantage of the structure of HiHi-saturated graphs to determine the saturation number of Rmin(H1,…,Hk).