DROPS

Document

DOI: 10.4230/LIPIcs.SWAT.2026.33

Polychromatic 2-Colorings with Bounded Discrepancy for Triangulations

Authors: Alma Arevalo Loyola, Ahmad Biniaz, Prosenjit Bose, and Thomas Shermer

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract

A polychromatic 2-coloring of a triangulation is a 2-coloring of the vertices such that no face is monochromatic. The discrepancy of a coloring is the maximum difference between the sizes of the color classes. Asayama and Matsumoto (Graphs and Combinatorics, 2022) proved that every triangulation admits a polychromatic 2-coloring with discrepancy at most (5n-16)/9, and that there exists a class of triangulations for which every polychromatic 2-coloring has discrepancy at least n/3 - 2, where n is the number of vertices. We improve the upper bound, showing that every triangulation admits a polychromatic 2-coloring with discrepancy at most (3n-16)/7 and such a 2-coloring can be computed in quadratic time. We also show a discrepancy of at most n-4M/3 for triangulations with a matching of size M. This implies, for example, that Delaunay triangulations admit a discrepancy of at most n/3. We provide a linear-time algorithm to compute a 2-coloring whose discrepancy is at most (5n-24)/7.

Cite as

Alma Arevalo Loyola, Ahmad Biniaz, Prosenjit Bose, and Thomas Shermer. Polychromatic 2-Colorings with Bounded Discrepancy for Triangulations. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 33:1-33:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{loyola_et_al:LIPIcs.SWAT.2026.33,
  author =	{Loyola, Alma Arevalo and Biniaz, Ahmad and Bose, Prosenjit and Shermer, Thomas},
  title =	{{Polychromatic 2-Colorings with Bounded Discrepancy for Triangulations}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{33:1--33:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.33},
  URN =		{urn:nbn:de:0030-drops-260691},
  doi =		{10.4230/LIPIcs.SWAT.2026.33},
  annote =	{Keywords: polychromatic coloring, triangulation, balanced coloring, matching}
}

Search Results

Documents authored by Loyola, Alma Arevalo

Polychromatic 2-Colorings with Bounded Discrepancy for Triangulations

Abstract

Cite as

Thanks for your feedback!

Could not send message