近日，我校计算科技研究院朱恩强教授和邵泽辉教授在数学-应用数学国际顶级期刊《Applied Mathematics and Computation》上，以广州大学作为第一署名单位发表了计算科学领域的重要分支-图着色理论方面的研究成果“On acyclically 4-colorable maximal planar graphs”。

众所周知，作为世界近代三大数学难题之一的四色猜想至今仍没给出数学方法的理论证明。在长达166年的四色猜想证明道路中，产生了诸多着色相关的重要理论体系，无圈着色就是其中的一个。图的无圈着色要求对图的顶点着色时着任意两种颜色的顶点不形成圈，自1973年由Grünbaum提出至今，已取得了丰富的研究成果。由于四色猜想的研究对象是平面图，所以关于平面图无圈着色的研究更具吸引力。学者们证明了任意平面图都是无圈5-可着色的，并发现了不含无圈4-着色的平面图，这说明无圈4-可着色平面图应具有某些特殊的性质。所以，学者们转向了对无圈4-着色的研究，特别是对无圈4-可着色平面图的结构的刻画。

 朱恩强教授和邵泽辉教授的论文在“任意无圈4-可着色极大平面图至少含有4个奇-点”这一前期成果的基础上，进一步研究了恰含4个奇-点的无圈4-可着色极大平面图的结构和性质。通过引入局部均匀着色，刻画了奇-度顶点和无圈着色之间的关系。通过探讨平面图与其对偶图之间的关系，借助于扩4-轮运算技巧，给出了一个判定奇-度顶点含4-圈的极大平面图是无圈4-可着色的充分必要条件，并给出了此类图的计数公式。

 该研究成果揭示了无圈4-可着色极大平面图的结构性质，对于图的无圈着色、四色猜想等方面的研究具有重要的理论意义。

（供稿：计算科技研究院  编辑：杨春荣）