On proper colorings of hypergraphs

N. V. Gravin ; D. V. Karpov

Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part III, Tome 391 (2011), pp. 79-89

Résumé

Let $\mathcal H$ be a hypergraph with maximal vertex degree $\Delta$, such that each hyperedge of it has at least $\delta$ vertices. Let $k=\lceil\frac{2\Delta}\delta\rceil$. We prove that $\mathcal H$ admits a proper vertex coloring with $k+1$ colors, (i.e., in any hyperedge there should be at least two vertices of different colors). For $k\ge3$ and $\delta\ge3$ we prove that $\mathcal H$ admits a proper vertex coloring with $k$ colors. For a graph $G$ set $k=\lceil\frac{2\Delta(G)}{\delta(G)}\rceil$. As a corollary we derive that there exists a proper dynamic coloring of the graph $G$ with $k+1$ colors, and for $k\ge3$ and $\delta(G)\ge3$ – with $k$ colors.