Paper by Erik D. Demaine

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.

BibTeX

@InProceedings{MFCS2000,
  AUTHOR        = {Therese C. Biedl and Eowyn \v{C}enek and Timothy M. Chan
                   and Erik D. Demaine and Martin L. Demaine and
                   Rudolf Fleischer and Ming-Wei Wang},
  TITLE         = {Balanced $k$-Colorings},
  BOOKTITLE     = {Proceedings of the 25th International Symposium on
                   Mathematical Foundations of Computer Science (MFCS 2000)},
  BOOKURL       = {http://www.mfcs.sk/},
  SERIES        = {Lecture Notes in Computer Science},
  SERIESURL     = {http://www.springer.de/comp/lncs/},
  VOLUME        = 1893,
  MONTH         = {August 28--September 1},
  ADDRESS       = {Bratislava, Slovak Republic},
  YEAR          = 2000,
  PAGES         = {202--211},

  length        = {10 pages},
  papers        = {BalancedColoringDM; BalancedColoringTR},
  copyright     = {The paper is \copyright Springer-Verlag.},
  doi           = {https://dx.doi.org/10.1007/3-540-44612-5_16},
  dblp          = {https://dblp.org/rec/conf/mfcs/BiedlCCDDFW00},
  comments      = {This paper is also available from <A HREF="https://doi.org/10.1007/3-540-44612-5_16">SpringerLink</A>.},
}

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

Comments:

This paper is also available from SpringerLink.

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)