Abstract of Paper

Balanced $k$-Colorings
by T.C. Biedl, E. Cenek, T.M. Chan, E.D. Demaine, M.L. Demaine, R. Fleischer, Ming-Wei Wang

Abstract:

While discrepancy theory is normally only studied in the context of
$2$-colorings, we explore the problem of $k$-coloring, for $k\geq 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.