Color-bounded hypergraphs, II: Interval hypergraphs and hypertrees

A color-bounded hypergraph is a hypergraph (set system) with vertex set XX and edge set E={E1,…,Em}E={E1,…,Em}, together with integers sisi and titi (1≤si≤ti≤|Ei|1≤si≤ti≤|Ei|) for i=1,…,mi=1,…,m. A vertex coloring φφ is feasible if the number of colors occurring in edge EiEi satisfies si≤|φ(Ei)|≤tisi≤|φ(Ei)|≤ti, for every i≤mi≤m.In this paper we point out that hypertrees–hypergraphs admitting a representation over a (graph) tree where each hyperedge EiEi 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 (si,ti)=(2,|Ei|)(si,ti)=(2,|Ei|), while ‘C-edge’ assumes (si,ti)=(1,|Ei|−1)(si,ti)=(1,|Ei|−1)–the differences are rather significant.