Journal
RANDOM STRUCTURES & ALGORITHMS
Volume -, Issue -, Pages -Publisher
WILEY
DOI: 10.1002/rsa.21190
Keywords
coloring; hypergraphs; Lovasz local lemma
Ask authors/readers for more resources
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.
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available