Improved vertex coloring method reduces imbalance in triangle networks
Polychromatic 2-colorings with Bounded Discrepancy for Triangulations
Computational Geometry
Summary
The paper studies a way to color the points (vertices) of a triangle-filled network so that no triangle has all points the same color, using just two colors. The goal is to keep the number of points in each color group balanced, minimizing how uneven the groups are. The authors improved previous results by showing how to achieve a better balance between the two colors and provided efficient algorithms to find these colorings. They also connected their work to special types of triangle networks called Delaunay triangulations and linked their findings to recent results on four-colorings of these graphs.
What this means in practice
- •For graph algorithm developers: Implement more efficient and balanced vertex colorings for triangulation-based graph problems using the provided quadratic and linear-time algorithms.
- •For computational geometry engineers: Improve mesh coloring schemes for Delaunay triangulations to optimize applications relying on balanced bipartite vertex assignments.
Authors
Alma Arevalo Loyola, Ahmad Biniaz, Prosenjit Bose, Thomas Shermer
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 $\tfrac{5n-16}{9}$, and that there exists a class of triangulations for which every polychromatic $2$-coloring has discrepancy at least $\tfrac{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 $\tfrac{3n-16}{7}$ and such a $2$-coloring can be computed in quadratic time. We also show a discrepancy of at most $n-\tfrac{4M}{3}$ for triangulations with a matching of size $M$. This implies, for example, that Delaunay triangulations admit a discrepancy of at most $\tfrac{n}{3}$. We provide a linear-time algorithm to compute a $2$-coloring whose discrepancy is at most $\tfrac{5n-24}{7}$. One of our results shows that any proper four coloring with the largest color class of size $\frac{n}{2}$ would imply a $2$-coloring with discrepancy at most $\frac{n}{3}$. The existence of such a proper coloring has been recently confirmed by Kawarabayashi, Yoneda, and Yoneda (arXiv 2026). Therefore the two results together confirm the discrepancy of at most $\frac{n}{3}$ for triangulations.