Abstract:
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.
Key words and phrases:hypergraph, proper coloring, dynamic coloring.