2002/02/22 by Raphael Yuster, Yuster, Raphael
Mathematics · #05C15 #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #math.CO #msc:05C15
paper · pdf · doi:10.48550/arxiv.math/0202230
10 Pages
arxiv created 2002/02/22 · openalex publication_date 2002/02/22 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let H be a k-uniform hypergraph with n vertices. A \em strong r-coloring is a partition of the vertices into r parts, such that each edge of H intersects each part. A strong r-coloring is called \em equitable if the size of each part is \lceil n/r \rceil or \lfloor n/r \rfloor. We prove that for all a ≥ 1, if the maximum degree of H satisfies Δ(H) ≤ ka then H has an equitable coloring with (k)/(a ln k)(1-ok(1)) parts. In particular, every k-uniform hypergraph with maximum degree O(k) has an equitable coloring with (k)/(ln k)(1-ok(1)) parts. The result is asymptotically tight. The proof uses a double application of the non-symmetric version of the Lovász Local Lemma.