Premium
Partitions of hypergraphs under variable degeneracy constraints
Author(s) -
Schweser Thomas,
Stiebitz Michael
Publication year - 2021
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22575
Subject(s) - hypergraph , degeneracy (biology) , combinatorics , mathematics , vertex (graph theory) , disjoint sets , sequence (biology) , degenerate energy levels , discrete mathematics , graph , physics , bioinformatics , genetics , quantum mechanics , biology
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 H and a sequence f = ( f 1 , f 2 , … , f p ) of p ≥ 1 vertex functionsf i : V ( H ) → N 0such thatf 1 ( v ) + f 2 ( v ) + ⋯ + f p ( v ) ≥ d H ( v )for all v ∈ V ( H ) , we want to find a sequence ( H 1 , H 2 , … , H p ) of vertex disjoint induced subhypergraphs containing all vertices of H such that each hypergraph H i is strictly f i ‐degenerate, that is, for every nonempty subhypergraph H ′ ⊆ H i there is a vertex v ∈ V ( H ′ ) such that d H ′( v ) < f i ( v ) . Our main result in this paper says that such a sequence of hypergraphs exists if and only if ( H , f ) 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.