Coloring simple hypergraphs

2013-06-27T00:00:00Z (GMT) by Alan Frieze Dhruv Mubayi

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.