Color-bounded hypergraphs, III: Model comparison
Csilla Bujtás, Źsolt Tuza · Applicable Analysis and Discrete Mathematics · 2007
Generalizing previous models of hypergraph coloring - due to Voloshin Drgas-Burchardt and Lazuka, and the present authors - in this paper we introduce and study the structure class that we call stably bounded hypergraphs. In this model, a hypergraph is viewed as a six-tuple H = (X, E s, t, a, b), where s, t, a, b: E → N are given integer-valued functions on the edge set. A mapping ': X ! N is a proper vertex coloring if it satisfies the following conditions for each edge E Є ε: the number of colors in E is at least s(E) and at most t(E), while the largest number of vertices having the same color inside E is at least a(E) and at most b(E). Taking dirent subsets of {s, t, a, b} (as combinations of nontrivial conditions on colorability) result in a hierarchy of structure classes with respect to vertex coloring. The main issue of this paper is to carry out a detailed analysis of how those classes are related. This includes the study of 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 under the dirent combinations of color-bound conditions, or restricting the edge sizes. Furthermore, substantial change is observed concerning the algorithmic complexity of recognizing hypergraphs that are uniquely colorable and Ф(H) = { |X| - 1}.