Generalized Hypergraph Coloring

Schweser, Thomas 

Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 1, pp. 103-121

Résumé

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.

Détail

Keywords: hypergraph decomposition, vertex partition, degeneracy, coloring of hypergraphs, hypergraph properties