Approximability of the upper chromatic number of hypergraphs

A C-coloring of a hypergraph $\mathcal{H}=(X,\mathcal{E})$ is a vertex coloring $\phi :X\to \mathbb{N}$ such that each edge $E\in \mathcal{E}$ has at least two vertices with a common color. The related parameter $\overline{\chi}({\cal H})$,calledtheupperchromaticnumberof${\cal H}$, is the maximum number of colors can be used in a C-coloring of $\mathcal{H}$. A hypertree is a hypergraph which has a host tree $T$ such that each edge $E\in \mathcal{E}$ induces a connected subgraph in $T$. Notations $n$ and $m$ stand for the number of vertices and edges, respectively, in a generic input hypergraph. We establish guaranteed polynomial-time approximation ratios for the difference $n-\bar{\chi }(\mathcal{H})$, which is $2+2\ln (2m)$ on hypergraphs in general, and $1+\ln m$ on hypertrees. The latter ratio is essentially tight as we show that $n-\bar{\chi }(\mathcal{H})$ cannot be approximated within $(1-ϵ)\ln m$ on hypertrees (unless ${\sf NP} \subseteq {\sf DTIME} (n^{{\cal O}(log;log; n)})$)\mathrm{.}Furthermore,$\overline{\chi}({\cal H})$doesnothave${\cal O}(n^{1-\epsilon})$-approximation and cannot be approximated within additive error $o(n)$ on the class of hypertrees (unless $\mathsf{P}=\mathsf{N}\mathsf{P}$).