Balanced Polychromatic 2-Coloring of Triangulations
Balanced Polychromatic 2-Coloring of Triangulations
复制标题
DOI：
10.1007/s00373-021-02420-8
复制
发表时间：
2021-12
影响因子：
0.7
通讯作者：
Yoshihiro Asayama;Naoki Matsumoto
中科院分区：
文献类型：
--
作者：
Yoshihiro Asayama;Naoki Matsumoto
众所周知，闭曲面上的每个三角剖分都有一个跨度四边形Q，特别是，如果是球体，则Q 是二分的。换句话说，球体上的每个三角剖分都具有多色 2 着色，这是没有单色面的封闭表面上的图形的（不一定是正确的）2 着色。在本文中，我们考虑图的多色2着色的平衡性，即每个颜色类的大小差异是否最多为1。我们验证每个 3 色三角剖分都具有平衡的多色 2 色。另一方面，我们构造了一个无限族的三角剖分 G，其阶次非球面，使得对于 G 的每个多色 2 着色，颜色类的大小至少不同。然后我们推测球体上的每个三角剖分都具有多色 2 着色，其颜色类别的大小最多相差顶点数量的三分之一，并且我们给出了该猜想的部分解。
It is well-known that every triangulation on a closed surfacehas a spanning quadrangulationQ, and in particular,Qis bipartite ifis the sphere. In other words, every triangulation on the sphere has a polychromatic 2-coloring, which is a (not necessarily proper) 2-coloring of a graph on a closed surface without a monochromatic face. In this paper, we consider the balancedness of a polychromatic 2-coloring of graphs, that is, whether the difference in size of each color class is at most one. We verify that every 3-colorable triangulation has a balanced polychromatic 2-coloring. On the other hand, we construct an infinite family of triangulationsGwith ordernon the sphere such that for every polychromatic 2-coloring ofG, the size of color classes differs at least. Then we 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, and we give partial solutions for the conjecture.