Gallai theorems for graphs, hypergraphs, and set systems (Q804601)

\textit{T. Gallai} presented in [Ann. Univ. Sci. Budapest, Rolando Eötvös, Sect. Math. 2, 133-138 (1959; Zbl 0094.361)] his now classical theorem, involving the vertex covering number \(\alpha_ 0\), the vertex independence number \(\beta_ 0\), the edge covering number \(\alpha_ 1\), and the maximum matching (or edge independence) number \(\beta_ 1:\) Theorem. For any nontrivial, connected graph \(G=(V,E)\) with p vertices, \(\alpha_ 0+\beta_ 0=\alpha_ 1+\beta_ 1=p.\) Since then quite a large number of similar results and generalizations of this theorem have been obtained, which we will call `Gallai Theorems'. A typical Gallai theorem has the form: \(\alpha +\beta =p\), where \(\alpha\) and \(\beta\) are numerical maximum or minimum functions of some type defined on the class of connected graphs and p denotes the number of vertices in a graph. This paper is an attempt to collect and unify results of this type. In particular, we present two general theorems which encompass nearly all of the existing Gallai theorems. The first theorem is based on hereditary properties of set systems, while the second is based on partition of vertices into subgraphs having treelike properties. We also present a variety of new Gallai theorems (one of which is not a corollary of either of the two above mentioned generalizations), as well as a number of other new results.