pith. sign in

arxiv: 1111.1558 · v1 · pith:JDZQKA2Wnew · submitted 2011-11-07 · 🧮 math.CO

On proper colorings of hypergraphs

classification 🧮 math.CO
keywords deltacolorshypergraphmathcalpropervertexadmitscoloring
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.