Color-bounded hypergraphs, IV: Stable colorings of hypertrees

We consider vertex colorings of hypergraphs in which lower and upper bounds are prescribed for the largest cardinality of a monochromatic subset and/or of a polychromatic subset in each edge. One of the results states that for any integers s ≥ 2 and a ≥ 2 there exists an integer f ( s , a ) with the following property. If an interval hypergraph admits some coloring such that in each edge E i at least a prescribed number s i ≤ s of colors occur and also each E i contains a monochromatic subset with a prescribed number a i ≤ a of vertices, then a coloring with these properties exists with at most f ( s , a ) colors. Further results deal with estimates on the minimum and maximum possible numbers of colors and the time complexity of determining those numbers or testing colorability, for various combinations of the four color bounds prescribed. Many interesting problems remain open.