摘要
四色猜想是指平面图的色数不超过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.
出处
《计算机学报》
EI
CSCD
北大核心
2015年第8期1680-1704,共25页
Chinese Journal of Computers
基金
国家"九七三"重点基础研究发展规划项目基金(2013CB32960
2013CB329602)
国家自然科学基金(60974112
30970960)资助~~
关键词
极大平面图
度序列
HAMILTON性
色多项式
计数
生成运算系统
翻转
分解
生成树
算法
maximal planar graph
degree sequence
Hamilton characteristic
chromatic polynomial
enumeration
generating operation system
flip
decomposition
spanning tree
algorithm
