运用权转移方法研究平面图的若干染色问题

图的染色是图论研究的重要内容，在现代计算机科学、信息科学等领域有着十分广泛的应用，一直得到国内外同行的极大关注。而平面图的染色问题一直是图论界的热点与难点。自Appel与Haken运用Discharging方法证明了四色定理后，Discharging方法在平面图的研究中起到了非常重要的作用。本项目主要运用此方法来研究平面图的无圈染色、星染色以及边面染色。首先探讨无圈点列表色数与圈长之间的关系，找到更多的平面图类满足Borodin等人提出的关于平面图是无圈5-点列表染色的猜想。其次通过研究图的星染色，争取给出平面图紧的上界，完整刻画具有较小最大度图的星色数；最后力争解决Sanders-Zhao提出的平面图边面全染色猜想。同时研究可嵌入高维曲面（如环面、仿射平面）图的边面全染色问题，推广平面图边面全染色的一些结果到曲面图上去。拟在三年内发表8篇左右被SCI检索的期刊论文。

图的染色是图论研究的重要内容，在现代计算机科学、信息科学等领域有着广泛的应用，近年来得到国内外同行的高度重视。本项目主要运用Discharging方法来研究图的无圈点列表染色、星列表染色、边面染色、点荫度以及非正常顶点列表染色。证明了不包含4-圈相邻于长度为3,4,5,6-圈平面图是无圈6-点列表可染的。给出了当前满足Montassier-Raspaud-Wang无圈4-点列表染色猜想的最好结果，即：证明了不包含4-圈和5-圈的平面图是无圈4-点列表可染的。研究了稀疏图的星列表色数。证明了环面Subcubic图的星列表色数至多为6，并通过例子说明上界6是最优的。证明了最大度为4或5的极大平面图满足Sanders-Zhao边面染色猜想，刻画了最大度为6的哈林图的边面列表色数。彻底解决了Raspaud-Wang点荫度猜想，提供了满足平面图列表(1,1,1)-染色猜想的若干充分条件。立项以来，项目组成员在国内外学术刊物上发表SCI论文9篇，获得浙江省自然科学学术奖一等奖1项和浙江省科学技术二等奖1项。