Saturation and semisaturation of oriented graphs
Abstract
We consider a natural extension of the classical saturation problem to oriented graphs, defined as the minimum number of edges in an oriented graph H on n vertices that avoids a fixed oriented graph G, but adding any missing edge to H creates a copy of G. Our main result shows that saturation functions of oriented graphs attain at least four distinct orders of magnitude. In particular, if G is acyclic, then its saturation function is bounded if and only if G contains an isolated edge; otherwise, it is linear. Certain tournaments together with an isolated edge give further infinite examples of bounded and linear saturation functions. Two additional orders of magnitude are Θ(n √(log n)) and Θ(n log n). For these two, the lower bounds are obtained by adapting a recently developed approach for the saturation problem in edge-ordered graphs, while the matching upper bounds are constructive. Finally, we study the semisaturation problem, in which we require only that adding any missing edge to H creates a copy of G. We completely characterize the possible orders of magnitude: the semisaturation function is either bounded, linear, or Θ(n log n).
Related
- Degreewise Cut-Semigroup Saturation for K5-Minor-Free Graphs and Seymour's Planar Edge-Colouring Conjecture
- The Plane-Saturation Ratio of Planar Graphs
- Ramsey--Turán Factors of Non-directed Oriented Cycles in Oriented Graphs
- Oriented paths with two blocks in bipartite oriented graphs
- Saturation numbers for joins with graphs containing isolated vertices
BibTeX
@misc{boskovic2026saturation,
title = {{Saturation and semisaturation of oriented graphs}},
author = {Vladimir Bošković and Balázs Keszegh},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.18600},
eprint = {2610.18600},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.18600},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Saturation and semisaturation of oriented graphs
AU - Vladimir Bošković
AU - Balázs Keszegh
PY - 2026
DA - 2026/10/13
PB - arXiv
DO - 10.48550/arxiv.2610.18600
UR - https://arxiv.org/abs/2610.18600
AB - We consider a natural extension of the classical saturation problem to oriented graphs, defined as the minimum number of edges in an oriented graph H on n vertices that avoids a fixed oriented graph G, but adding any missing edge to H creates a copy of G. Our main result shows that saturation functions of oriented graphs attain at least four distinct orders of magnitude. In particular, if G is acyclic, then its saturation function is bounded if and only if G contains an isolated edge; otherwise, it is linear. Certain tournaments together with an isolated edge give further infinite examples of bounded and linear saturation functions. Two additional orders of magnitude are Θ(n √(log n)) and Θ(n log n). For these two, the lower bounds are obtained by adapting a recently developed approach for the saturation problem in edge-ordered graphs, while the matching upper bounds are constructive. Finally, we study the semisaturation problem, in which we require only that adding any missing edge to H creates a copy of G. We completely characterize the possible orders of magnitude: the semisaturation function is either bounded, linear, or Θ(n log n).
ER -