file.pdf (404.51 kB)
Coloring simple hypergraphs
Fix an integer k⩾3k⩾3. A k-uniform hypergraph is simple if every two edges share at most one vertex. We prove that there is a constant c depending only on k such that every simple k-uniform hypergraph H with maximum degree Δ has chromatic number satisfying
This implies a classical result of Ajtai, Komlós, Pintz, Spencer and Szemerédi and its strengthening due to Duke, Lefmann and Rödl. The result is sharp apart from the constant c.