**Reference**:- Therese C. Biedl, Eowyn Čenek, Timothy M. Chan, Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer, and Ming-Wei Wang, “Balanced
*k*-Colorings”,*Discrete Mathematics*, volume 254, 2002, pages 19–32. **Abstract**:-
While discrepancy theory is normally only studied in the context of
2-colorings, we explore the problem of
*k*-coloring, for*k*≥ 2, a set of vertices to minimize imbalance among a family of subsets of vertices. The*imbalance*is the maximum, over all subsets in the family, of the largest difference between the size of any two color classes in that subset. The*discrepancy*is the minimum possible imbalance. We show that the discrepancy is always at most 4*d*− 3, where*d*(the “dimension”) is the maximum number of subsets containing a common vertex. For 2-colorings, the bound on the discrepancy is at most max {2*d*− 3, 2}. Finally, we prove that several restricted versions of computing the discrepancy are NP-complete. **Copyright**:- The paper is \copyright Elsevier Science B.V.
**Length**:- The paper is 13 pages.
**Availability**:- The paper is available in PostScript (257k) and gzipped PostScript (89k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- MFCS2000 (Balanced
*k*-Colorings) - BalancedColoringTR (Balanced
*k*-Colorings)

See also other papers by Erik Demaine.

Last updated July 23, 2024 by Erik Demaine.