TY - GEN

T1 - Balanced k-colorings

AU - Biedl, Therese C.

AU - Čenek, Eowyn

AU - Chan, Timothy M.

AU - Demaine, Erik D.

AU - Demaine, Martin L.

AU - Fleischer, Rudolf

AU - Wang, Ming Wei

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2000.
Copyright:
Copyright 2016 Elsevier B.V., All rights reserved.

PY - 2000

Y1 - 2000

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84959204758&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84959204758&partnerID=8YFLogxK

U2 - 10.1007/3-540-44612-5_16

DO - 10.1007/3-540-44612-5_16

M3 - Conference contribution

AN - SCOPUS:84959204758

SN - 3540679014

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 202

EP - 211

BT - Mathematical Foundations of Computer Science 2000 - 25th International Symposium, MFCS 2000 , Proceedings

A2 - Rovan, Branislav

A2 - Nielsen, Mogens

PB - Springer

T2 - 25th International Symposium on Mathematical Foundations of Computer Science, MFCS 2000

Y2 - 28 August 2000 through 1 September 2000

ER -