Authors: T. Schweser Title: Generalized hypergraph coloring Source: Discussiones Mathematicae Graph Theory Received 18.04.2018, Revised 23.08.2018, Accepted 23.08.2018, doi: 10.7151/dmgt.2168 | |
Abstract: A smooth hypergraph property 𝒫 is a class of hypergraphs that is hereditary and non-trivial, i.e., closed under induced subhypergraphs and it contains a non-empty hypergraph but not all hypergraphs. In this paper we examine 𝒫-colorings of hypergraphs with smooth hypergraph properties 𝒫. A 𝒫-coloring of a hypergraph H with color set C is a function φ:V(H) → C such that H[φ^{-1}(c)] belongs to 𝒫 for all c ∈C. Let L: V(H) → 2^{C} be a so called list-assignment of the hypergraph H. Then, a (𝒫,L)-coloring of H is a 𝒫-coloring φ of H such that φ(v) ∈L(v) for all v ∈V(H). The aim of this paper is a characterization of (𝒫,L)-critical hypergraphs. Those are hypergraphs H such {that} H-v is (𝒫,L)-colorable for all v ∈V(H) but H itself is not. Our main theorem is a Gallai-type result for critical hypergraphs, which implies a Brooks-type result for (𝒫,L)-colorable hypergraphs. In the last section, we prove a Gallai-type bound for the degree sum of (𝒫,L)-critical locally simple hypergraphs. | |
Keywords: hypergraph decomposition, vertex partition, degeneracy, coloring of hypergraphs, hypergraph properties | |
Links: |