SCIENCE@home

Equitable Coloring of k-Uniform Hypergraphs

R. Yuster

Published 2002 in SIAM Journal on Discrete Mathematics

ABSTRACT

Let H be a k-uniform hypergraph with n vertices. A 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 equitable if the size of each part is $\lceil n/r \rceil$ or $\lfloor n/r \rfloor$. We prove that for all $a \geq 1$, if the maximum degree of H satisfies $\Delta(H) \leq k^a$, then H has an equitable coloring with $\frac{k}{a \ln k}(1-o_k(1))$ parts. In particular, every k-uniform hypergraph with maximum degree O(k) has an equitable coloring with $\frac{k}{\ln k}(1-o_k(1))$ parts. The result is asymptotically tight. The proof uses a double application of the nonsymmetric version of the Lovasz local lemma.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-10 of 10 references · Page 1 of 1

CITED BY