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

图的染色是图论研究的重要内容,在现代计算机科学、信息科学、管理科学等领域有着十分广泛的应用，一直得到国内外同行的极大关注。图的存活率是一个新引进的图参量，在森林防火、疫情控制、计算机防毒等实际问题中有着很强的应用背景。本项目从图的结构性质入手，研究图的各种染色问题，如无圈点染色、无圈边染色、线性染色、星染色、列表染色等。力争解决或部分解决Borodin等人提出的关于平面图是无圈5-可选的猜想；围绕Alon-Sudakov-Zaks猜想，对一般图改进已知无圈边色数的上界，找到新的图类满足该猜想。研究图的防火问题，找出存活率渐近为正的新的更广泛的图类，回答是否绝大部分的图的存活率渐近为0的问题，推广防火问题到有向图上。研究超立方体网络、Star 等一些著名网络的距离标号数，争取改进已有的结果。拟在三年内完成学术论文20余篇，其中10篇以上发表在SCI杂志上。

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