Coloring simple hypergraphs
Alan Frieze
Dhruv Mubayi
10.1184/R1/6477059.v1
https://kilthub.cmu.edu/articles/journal_contribution/Coloring_simple_hypergraphs/6477059
<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>
2013-06-27 00:00:00
Hypergraph coloring
Semi-random method