Partitions of hypergraphs under variable degeneracy constraints
- The paper deals with partitions of hypergraphs into induced subhypergraphs satisfying constraints on their degeneracy. Our hypergraphs may have multiple edges, but no loops. Given a hypergraph and a sequence of vertex functions such that for all , we want to find a sequence of vertex disjoint induced subhypergraphs containing all vertices of such that each hypergraph is strictly ‐degenerate, that is, for every nonempty subhypergraph there is a vertex such that . Our main result in this paper says that such a sequence of hypergraphs exists if and only if is not a so‐called hard pair. Hard pairs form a recursively defined family of configurations, obtained from three basic types of configurations by the operation of merging a vertex. Our main result has several interesting applications related to generalized hypergraph coloring problems.
