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) → 2C 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:
PDF