嵌入图的全染色和线性荫度

Graph coloring and arbiricity are two important branches of graph theory research. In particular, they have attracted considerable attention in the latest decades. In this project, beginning with the study of structural properties of embedded graphs, we will investigate various coloring problems (e.g.,entire coloring, edge-face total coloring, vertex-edge total coloring) and arboricity problems (e.g., linear arboricity, linear 2-arboricity). Aiming at several well-known conjectures in the related fields and applying algebraic method, probabilistic analysis, discharging process and edge-partition technique, we characterize or bound some parameters for some embedded graphs. We try to show (or partically settle) the following problems: (1) A plane graph G different from K4 is (Δ+3)-entirely colorable; (2) An embedded graph G on the torus is (Δ+4)-entirely colorable; (3) A plane graph G with Δ=4,5 is (Δ+2)-edge-face totally colorable; (4) A plane graph G with Δ=7 is 8-edge-face totally coloriable; (5) A planar graph G with Δ=6 is 8-vertex-face totally colorable; (6) A toroidal graph G with Δ=11 is 12-vertex-face totally choosable. We will improve or give the upper bounds on the linear 2-arboticity of embedded graphs such as plane graphs, torodial graphs, projective planar graphs.

图的染色与荫度是图论研究的重要内容，近些年来更成为热点课题。本项目从图的结构性质入手，研究嵌入图的各种染色问题（包括完备染色、边-面全染色、点-面全染色）和荫度问题（包括线性荫度、线性2-荫度）。围绕着本领域的几个著名猜想，借助代数、概率、权转移、边分解等方法，对一些嵌入图的上述参数进行刻画或给出好的上界，分析其计算复杂性。在完备染色方面，证明或部分证明：不同于K4的平面图是(Δ+3)-完备可染的，环面嵌入图是(Δ+4)-完备可染的。在边-面全染色方面，证明：最大度为4或5的平面图是(Δ+2)-边-面全可染的，最大度为7的平面图是8-边-面全可染的。在点-边全染色方面，证明: 最大度为6的平面图是8-点-边全可染的，最大度为11的环面图是12-点-边全可选的。在图的荫度方面，改进或给出平面图、环面图、射影平面图等的线性2-荫度的上界。

图的染色与荫度是图论研究的重要内容,在现代计算机科学、信息科学、管理科学等领域有着十分广泛的应用。本项目从图的结构性质入手，研究图的各种染色问题，包括嵌入图的完备染色和边面染色、图的强边染色和星边染色、图的无圈点染色和边染色、图的邻点可区别边染色和全染色、图的点荫度和线性荫度等，得到一些有意义的研究成果。证明了每个Δ≥20的2-连通平面图的完备色数是Δ+1, Δ≥16的2-连通平面图的边面色数是Δ; 证明了每个Δ ≤7的平面图是8-边面可染的，扩充了已知结果：每个Δ≥8的平面图是(Δ+1)-边面可染的; 证明了K4-minor-free图的强边色数至多为3Δ-2，完整刻画了外平面图的强边色数达到上界3Δ-3的极图；证明了4-正则图满足无圈边染色猜想和1-平面图族的无圈边色数不超过Δ+36；证明了1-平面图的无圈点色数至多为18，IC-平面图的无圈点色数至多为10，这些结果改进了Borodin等人于20年前得到的一个结论：1-平面图的无圈点色数至多为20；证明了平面图的线性2-荫度至多为{(Δ+1)/2}+6, 环面图的线性2-荫度至多为{(Δ+1)/2}+7, 1-平面图的线性2-荫度至多为{(Δ+1)/2}+14。此外考虑了平面图的列表染色和对角染色，引入和研究了图的距离2可区别边染色和严格邻点可区别边染色等问题。立项以来，项目组成员在国内外学术刊物上发表论文80篇，其中被 SCI 检索67篇，获教育部自然科学学术奖二等奖1项。