Generalized Hypergraph Coloring

A smooth hypergraph property \(\mathcal{P}\) 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 \(\mathcal{P}\)-colorings of hypergraphs with smooth hypergraph properties \(\mathcal{P}\). A \(\mathcal{P}\)-coloring of a hypergraph $H$ with color set $C$ is a function $\varphi : V(H) → C$ such that \(H\big[\varphi^{−1}(c)\big]\) belongs to \(\mathcal{P}\) for all $c ∈ C$. Let $L : V (H) → 2^C$ be a so called list-assignment of the hypergraph $H$. Then, a (\(\mathcal{P}, L\))-coloring of $H$ is a \(\mathcal{P}\)-coloring $\varphi$ of $H$ such that $\varphi(v) ∈ L(v)$ for all $v ∈ V (H)$. The aim of this paper is a characterization of (\(\mathcal{P}, L\))-critical hypergraphs. Those are hypergraphs $H$ such that $H − v$ is (\(\mathcal{P}, 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 (\(\mathcal{P}, L\))-colorable hypergraphs. In the last section, we prove a Gallai-type bound for the degree sum of (\(\mathcal{P}, L\))-critical locally simple hypergraphs.