On proper colorings of hypergraphs

Abstract

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.

10 pages, 3 figure

Cited by in corpus (1)

• On list chromatic numbers of 2-colorable hypergraphs