Balanced polychromatic 2-coloring of triangulations (Q2062902)

For a given graph \(G\), a polychromatic \(k\)-coloring of a graph \(G\) is a (not necessarily proper) vertex coloring of \(G\) such that all \(k\) colors appear on the boundary of each face of \(H\). A graph on a closed surface has a balanced polychromatic \(2\)-coloring which is a bisection, i.e., the difference in size of each color class is at most one. In this paper, the authors show that every \(3\)-colorable triangulation has a balanced polychromatic 2-coloring, and they construct an infinite family of triangulations \(G\) with order \(n\) on the sphere such that for every polychromatic \(2\)-coloring of \(G\), the size of color classes differs at least \(n/3-2\). This paper also proposes a conjecture that every triangulation on the sphere has a polychromatic \(2\)-coloring whose size of color classes differs at most one-third of the number of vertices. The authors verify the conjecture for two classes of graphs, i.e., triangulations on the plane of order \(n\ge 4\) with the minimum degree at least \(4\), and planar \(3\)-trees of order \(n\ge 4\) which is a planar graph obtained from the complete graph of order \(4\) on the plane by repeatedly inserting a vertex of degree \(3\) in a triangular face and joining it to vertices on the boundary of the corresponding face.