**Reference**:- Therese C. Biedl, Eowyn Čenek, Timothy M. Chan, Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer, and Ming-Wei Wang, “Balanced
*k*-Colorings”, in*Proceedings of the 25th International Symposium on Mathematical Foundations of Computer Science (MFCS 2000)*, Lecture Notes in Computer Science, volume 1893, Bratislava, Slovak Republic, August 28–September 1, 2000, pages 202–211. **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. **Comments**:- This paper is also available from the electronic LNCS volume as http://link.springer.de/link/service/series/0558/papers/1893/18930202.pdf.
**Copyright**:- The paper is \copyright Springer-Verlag.
**Length**:- The paper is 10 pages.
**Availability**:- The paper is available in PostScript (164k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- BalancedColoringDM (Balanced
*k*-Colorings) - BalancedColoringTR (Balanced
*k*-Colorings)

See also other papers by Erik Demaine.

Last updated January 15, 2021 by Erik Demaine.