2026-10-01T07:51:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26069 2026-09-23T23:59:31Z ddc:004 open_access

Polychromatic 2-Colorings with Bounded Discrepancy for Triangulations Loyola, Alma Arevalo Biniaz, Ahmad Bose, Prosenjit Shermer, Thomas polychromatic coloring triangulation balanced coloring matching 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alma Arevalo Loyola and Ahmad Biniaz and Prosenjit Bose and Thomas Shermer 2026 Is Part Of LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2026.33 urn:nbn:de:0030-drops-260691 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.33 eng https://creativecommons.org/licenses/by/4.0/legalcode