Color-bounded hypergraphs, II: Interval hypergraphs and hypertrees

摘要

A color-bounded hypergraph is a hypergraph (set system) with vertex set X and edge set epsilon = {E-1,..., E-m), together with integers s(i) and t(i) (1 <= s(i) <= t(i) <= |E-i|) for i = 1, ... , m. A vertex coloring phi is feasible if the number of colors occurring in edge E-i satisfies s(i) <= |phi(E-i)| <= t(i), for every i <= m. In this paper we point out that hypertrees - hypergraphs admitting a representation over a (graph) tree where each hyperedge E-i induces a subtree of the underlying tree - play a central role concerning the set of possible numbers of colors that can occur in feasible colorings. We also consider interval hypergraphs and circular hypergraphs, where the underlying graph is a path or a cycle, respectively. Sufficient conditions are given for a 'gap-free' chromatic spectrum; i.e., when each number of colors is feasible between minimum and maximum. The algorithmic complexity of colorability is studied, too. Compared with the 'mixed hypergraphs' - where 'D-edge' means (s(i), t(i)) = (2, |E-i|), while 'C-edge' assumes (s(i), t(i)) = (1, |E-i| - 1) - the differences are rather significant.