极大平面图理论研究进展

• 作者: 朱恩强 李泽鹏 许进
• 来源期刊: 计算机学报
• 学科: 数学
• 关键词: 极大平面图 度序列 Hamilton 性 色多项式 计数 生成运算系统 翻转 分解 生成树 算法
• 年，卷（期）: 2015,（8）
• 所属期刊栏目: 计算机理论与算法
• 页码范围: 1680-1704
• 页数: 25页
• 分类号: O157
• 字数: 24907字
• 语种: 中文
• DOI: 10.11897/SP.J.1016.2015.01680

摘要

四色猜想是指平面图的色数不超过4．实际上，四色猜想只需证明对极大平面图成立即可．正因为如此，从1891年至今，有众多学者从不同的角度展开了对极大平面图的研究．该文拟对其中的一些重要成果进行较为详细的综述，主要包括极大平面图的度序列问题、Hamilton 性、色多项式、生成运算系统、计数、翻转运算、分解与覆盖、生成树和算法等方面．在总结极大平面图研究现状的基础上，提出了一些与着色相关的问题，这些问题意在探索极大平面图的结构与着色之间的关系，有助于对四色问题的进一步研究．

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	许进	北京大学信息科学技术学院	33	247	8.0	15.0
5	李泽鹏	北京大学信息科学技术学院	3	15	2.0	3.0
9	朱恩强	北京大学信息科学技术学院	7	19	3.0	4.0