For a non-empty graph G, the saturation problem asks for the minimum number of edges in a graph H on n vertices, which does not contain G as a subgraph but adding any missing edge to H creates a copy of G. We address this question for vertex-ordered graphs and we show that their saturation functions are either bounded or linear. Furthermore, we find infinitely large families exhibiting both behaviours. We also study the saturation functions of edge-ordered graphs and we show that there is no such dichotomy by providing examples of edge-ordered graphs with superlinear saturation functions.
This is joint work with Balázs Keszegh.
Copyright. All Rights Reserved.