Maximum number of colors in hypertrees of bounded degree

The upper chromatic number $$\overline{\chi }(\mathcal{H})$$ χ ¯ ( H ) of a hypergraph $$\mathcal{H}=(X,\mathcal{E})$$ H = ( X , E ) is the maximum number of colors that can occur in a vertex coloring $$\varphi :X\rightarrow \mathbb {N}$$ φ : X → N such that no edge $$E\in \mathcal{E}$$ E ∈ E is completely multicolored. A hypertree (also called arboreal hypergraph) is a hypergraph whose edges induce subtrees on a fixed tree graph. It has been shown that on hypertrees it is algorithmically hard not only to determine exactly but also to approximate the value of $$\overline{\chi }$$ χ ¯ , unless $$\mathsf{P}=\mathsf{NP}$$ P = NP . In sharp contrast to this, here we prove that if the input is restricted to hypertrees $$\mathcal{H}$$ H of bounded maximum vertex degree, then $$\overline{\chi }(\mathcal{H})$$ χ ¯ ( H ) can be determined in linear time if an underlying tree is also given in the input. Consequently, $$\overline{\chi }$$ χ ¯ on hypertrees is fixed parameter tractable in terms of maximum degree. Copyright Springer-Verlag Berlin Heidelberg 2015