Coloring simple hypergraphs
FriezeAlan
MubayiDhruv
2013
<p>Fix an integer k⩾3k⩾3. A <em>k</em>-uniform hypergraph is simple if every two edges share at most one vertex. We prove that there is a constant <em>c</em> depending only on <em>k</em> such that every simple <em>k</em>-uniform hypergraph <em>H</em> with maximum degree Δ has chromatic number satisfying</p>
<a></a>
<p>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 <em>c</em>.</p>