Defective coloring of hypergraphs

We prove that the vertices of every (r+1)-uniform hypergraph with maximum degree Delta may be colored with c(Delta/d+1)(1/r) colors such that each vertex is in at most d monochromatic edges. This result, which is best possible up to the value of the constant c , generalizes the classical result of Erd & odblac;s and Lov & aacute;sz who proved the d=0 case.

Automated summary

In this paper, it is proved that the vertices of every (r+1)-uniform hypergraph with maximum degree Delta can be colored with a certain number of colors, such that each vertex is in at most d monochromatic edges. This result is a generalization of the classical result of Erdős and Lovász for the d=0 case.