Balanced k-colorings

Therese C. Biedl, Eowyn Čenek, Timothy M. Chan, Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer, Ming Wei Wang

Research output: Contribution to journalArticlepeer-review


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 4d - 3, where d (the "dimension") is the maximum number of subsets containing a common vertex. For 2-colorings, the bound on the discrepancy is almost max{2d - 3,2}. Finally, we prove that several restricted versions of computing the discrepancy are NP-complete.

Original languageEnglish (US)
Pages (from-to)19-32
Number of pages14
JournalDiscrete Mathematics
Issue number1-3
StatePublished - Jun 10 2002
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Balanced k-colorings'. Together they form a unique fingerprint.

Cite this