COLOR-BOUNDED HYPERGRAPHS, III: MODEL COMPARISON

Generalizing previous models of hypergraph coloring ￠ € ” due toVoloshin, Drgas-Burchardt and Lazuka, and the present authors ￠ € “ inthis paper we introduce and study the structure class that we call stablybounded hypergraphs. In this model, a hypergraph is viewed as a six-tupleH = (X, E, s, t, a, b), where s, t, a, b : E ! N are given integer-valued functionson the edge set. A mapping ' : X ! N is a proper vertex coloring if itsatisfies the following conditions for each edge E 2 E : the number of colorsin E is at least s(E) and at most t(E), while the largest number of verticeshaving the same color inside E is at least a(E) and at most b(E).Taking different subsets of {s, t, a, b} (as combinations of nontrivialconditions on colorability) result in a hierarchy of structure classes with respectto vertex coloring. The main issue of this paper is to carry out adetailed analysis of how those classes are related. This includes the studyof possible chromatic polynomials and ￠ € feasible sets ￠ € ￠ € ” that is, the set (H)of integers k such that H has a proper vertex coloring with exactly k colors ￠ € ” with or without assuming that the number of vertices is the same underthe different combinations of color-bound conditions, or restricting the edgesizes. Furthermore, substantial change is observed concerning the algorithmiccomplexity of recognizing hypergraphs that are uniquely colorable and(H) = { |X| - 1}.