**Reference**:- Therese C. Biedl, Eowyn Čenek, Timothy M. Chan, Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer, and Ming-Wei Wang, “Balanced
*k*-Colorings”, Technical Report CS-2000-08, Department of Computer Science, University of Waterloo, March 2000. **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. **Length**:- The paper is 11 pages.
**Availability**:- The paper is available in PostScript (204k) and gzipped PostScript (52k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- BalancedColoringDM (Balanced
*k*-Colorings) - MFCS2000 (Balanced
*k*-Colorings)

See also other papers by Erik Demaine.

Last updated December 5, 2021 by Erik Demaine.