极大平面图理论研究进展  

Research Progress on the Theory of Maximal Planar Graphs

作　　者：许进[1,2] 李泽鹏[1,2] 朱恩强[1,2] 

机构地区：[1]北京大学信息科学技术学院,北京100871 [2]北京大学高可信软件技术教育部重点实验室,北京100871

出　　处：《计算机学报》2015年第8期1680-1704,共25页Chinese Journal of Computers

基　　金：国家"九七三"重点基础研究发展规划项目基金(2013CB32960;2013CB329602);国家自然科学基金(60974112;30970960)资助~~

摘　　要：四色猜想是指平面图的色数不超过4.实际上,四色猜想只需证明对极大平面图成立即可.正因为如此,从1891年至今,有众多学者从不同的角度展开了对极大平面图的研究.该文拟对其中的一些重要成果进行较为详细的综述,主要包括极大平面图的度序列问题、Hamilton性、色多项式、生成运算系统、计数、翻转运算、分解与覆盖、生成树和算法等方面.在总结极大平面图研究现状的基础上,提出了一些与着色相关的问题,这些问题意在探索极大平面图的结构与着色之间的关系,有助于对四色问题的进一步研究.The Four-Color Conjecture says that the chromatic number of planar graphs is not more than 4.Indeed,it suffices to prove that each maximal planar graph is 4-clorable.For this reason,since 1891 many scholars have been devoted to the research on such graphs from different points of view.In this paper,some of important results with regard to maximal planar graphs are to be reviewed and analyzed in detail,including the problems of degree sequence,Hamilton characteristic,chromatic polynomial,generating operation system,enumeration,flip operation,decomposition and covering,spanning tree,and some algorithms.Based on the understanding of the research status of the maximal planar graphs,we propose several problems on such graphs in connection with their colorings.These problems intend to reveal the relationship between the structures and the colorings of maximal planar graphs,which may be usful for further study on the Four-Color Problem.

关 键 词：极大平面图 度序列 HAMILTON性 色多项式 计数 生成运算系统 翻转 分解 生成树 算法 

分 类 号：O157[理学—数学]