嵌套多芒星的全着色

来源：电子与信息学报杂志2026年第3期北京时间：

作者：苏榕进, 方刚, 朱恩强, 许进

单位：1.广州大学计算科技研究院 广州 5105552.广州大学计算机科学与网络工程学院 广州 5105553.北京大学高可信软件技术教育部重点实验室 北京 1008714.北京大学计算机学院 北京 100871

摘要：图G的k-全着色是指使用k种颜色对图的顶点与边同时进行着色，使得任意相邻的顶点、相邻的边，以及任意关联的顶点与边之间均着不同颜色。全着色猜想断言：任何简单图均存在(\begin{document}$\varDelta $\end{document}+2)-全着色，其中\begin{document}$\varDelta $\end{document}代表图的最大度。自该猜想提出以来，一直受到广泛关注，并取得了丰富的研究进展。然而，尽管经过数十年的努力，全着色猜想至今仍未得到完全证明，甚至对平面图情形亦不例外。目前，对于平面图，仅剩最大度为6且同时含有4-扇子结构，或最大平均度不低于23/5的图类尚未被证实。该文针对这类平面图的全着色展开研究，提出一类称为嵌套多芒星的图类，其最大度为6、包含4-扇子结构，且最大平均度不低于23/5。该文证明了全着色猜想在此类图上成立。特别地，发现一类属于I-型图的嵌套多芒星，即存在7-全着色。这一结果进一步推进了对平面图全着色问题的理解。

关键词：全着色, 平面图, 嵌套多芒星, I-型图

基金资助：国家自然科学基金(62272115, 62541308)