Let $\mathcal{ H}$ be a hypergraph of maximal vertex degree $\Delta$, such that each its hyperedge contains at least $\delta$ vertices. Let $k=\lceil\frac{ 2\Delta}{ \delta}\rceil$. We prove that (i) The hypergraph $\mathcal{ H}$ admits proper vertex coloring in $k+1$ colors. (ii) The hypergraph $\mathcal{ H}$ admits proper vertex coloring in $k$ colors, if $\delta\ge 3$ and $k\ge 3$. As a consequence of these results we derive upper bounds on the number of colors in dynamic colorings.

Categories: math.CO

On proper colorings of hypergraphs