Approximability of the upper chromatic number of hypergraphs

Abstract

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 }(\mathcal{H})$, called the upper chromatic number of $\mathcal{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-\overline{\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-\overline{\chi }(\mathcal{H})$ cannot be approximated within $(1-\epsilon )\ln m$ on hypertrees (unless $\mathsf{NP}\subseteq \mathsf{DTIME}(n^{\mathcal{O}(loglogn)})$). Furthermore, $\overline{\chi }(\mathcal{H})$ does not have $\mathcal{O}(n^{1-\epsilon })$-approximation and cannot be approximated within additive error $o(n)$ on the class of hypertrees (unless $\mathsf{P}=\mathsf{NP}$).

arXiv comment18 pages