Approximability of the upper chromatic number of hypergraphs

We establish guaranteed polynomial-time approximation ratios for the difference n−χ¯(H), which is 2+2ln(2m) on hypergraphs in general, and 1+lnm on hypertrees. The latter ratio is essentially tight as we show that n−χ¯(H) cannot be approximated within (1−ϵ)lnm on hypertrees (unless NP⊆DTIME(nO(loglogn))). Furthermore, χ¯(H) does not have O(n1−ϵ)-approximation and cannot be approximated within additive error o(n) on the class of hypertrees (unless P=NP).