Balanced k-colorings

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 at most max{2d—3, 2}. Finally, we prove that several restricted versions of computing the discrepancy are NP-complete.

Original languageEnglish (US)
Title of host publicationMathematical Foundations of Computer Science 2000 - 25th International Symposium, MFCS 2000 , Proceedings
EditorsBranislav Rovan, Mogens Nielsen
Number of pages10
ISBN (Print)3540679014
StatePublished - 2000
Externally publishedYes
Event25th International Symposium on Mathematical Foundations of Computer Science, MFCS 2000 - Bratislava, Slovakia
Duration: Aug 28 2000Sep 1 2000

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other25th International Symposium on Mathematical Foundations of Computer Science, MFCS 2000
City Bratislava

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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

Cite this