图的无圈染色和存活率研究

图的染色、标号与存活率是图论研究的重要内容, 在现代计算机科学、信息科学、管理科学等领域有着十分广泛的应用，近些年来得到了国内外同行的高度重视。本项目从图的结构性质入手，研究图的各种染色与标号问题，如无圈染色、邻点区别边染色和全染色、平面图的各种全染色、存活率等。证明了4-正则图、没有3-圈、4-圈、5-圈、或6-圈的平面图等满足著名的Alon-Sudakov-Zaks无圈边染色猜想，对平面图的无圈边色数的上界从△+12改进到△+7。证明了最大度为6的平面图是8-边-面可染的，最大度至少为9的平面图是(△+2)-完备可染的，特别是彻底解决了著名的Kronk和Mitchem关于平面图完备染色猜想，即证明了：每个平面图是(△+4)-完备可染的。对一般图给出邻点区别边色数和全色数好的上界，刻画了外平面图、大围长平面图、有较小最大平均度的图的邻点区别边色数和全色数。给出图的存活率的新概念，建立一些稀疏图的存活率的下界，特别是证明了平面图的3-存活率大于一个正的常数。立项以来，项目组成员在国内外学术刊物上发表论文 60 篇，其中被 SCI 检索 45 篇，获得浙江省自然科学学术奖一等奖1项和浙江省科学技术二等奖1项。