平面图的边面染色和完备染色

Research on various parameters of plane graphs is an important branch of graph theory, which is one of the hotspots and difficulties in the chromatic graph theory and has attracted considerable attention in the latest decades. In this project, we will apply the discharging method and various coloring techniques to study the edge-face coloring and entire coloring of graphs. Based on the current results, we study the following problems: (1) We study the edge-face coloring of plane graphs, and strive to determine a tight upper bound of edge-face chromatic number for the plane graphs with the maximum degree no more than 6 and at least 4; We try to determine the least integer C such that every 2-connected simple plane graph with the maximum degree at least C is edge-face ∆-colorable. (2) Aiming at the Wang-Zhu conjecture, which says that if G is a plane graph with the maximum degree at least 3 and G≠K4, then it is entirely (the maximum degree +3)-colorable, we will try to verify whether the plane graph with the maximum degree at most 7 satisfies the conjecture. (3) In order to investigate the entire coloring of 2-connected plane graphs, we attempt to find a minimal positive integer C, such that the chromatic number is the tight lower bound the maximum degree plus 1 when the maximum degree is at least C. (4) We also study the list entire coloring and the entire coloring of toroidal graphs. At least 6 papers are completed after the project is finished, where at least half papers are indexed by SCI.

平面图的各种染色参数研究是图的染色理论中的热点和难点之一，得到国内外同行的广泛关注。本项目将从图的结构性质出发，运用权转移以及各种染色技巧来研究图的边面染色和完备染色。在现有的工作基础上,深入研究以下几个问题：（1）研究平面图的边面染色问题，力争确定4≤最大度≤6的平面图的边面色数紧的上界；同时研究2-连通的平面图的边面色数，尝试确定一个最小的正整数C，使得最大度≥C时，边面色数是最大度。（2）围绕Wang和Zhu提出的猜想：对于任意最大度≥3且G≠K4的平面图G都是完备(最大度+3)-可染的，我们尝试研究最大度≤7的平面图是否满足此猜想。（3）研究2-连通的平面图的完备染色，尝试确定一个最小的正整数C，使得最大度≥C时，完备色数达到紧的下界(最大度+1)。（4）研究完备列表染色和环面图的完备染色。拟在三年内完成学术论文6篇，其中半数以上发表在SCI期刊上。

本项目从图的结构性质入手，研究图的边面染色和完备染色，以及图的线性2-荫度。主要研究平面图的边面染色和完备染色，环面图的完备染色，以及平面图和1-平面图的线性2-荫度。特别是在限制最大度的条件下，尝试确定图的边面色数，完备色数和线性2-荫度紧的上界。结合图的结构性质和权转移方法，我们得到如下一些结论： 证明了最大度至少为20的2-连通的简单平面图的完备色数等于∆+1，特别地，∆+1是平面图的紧的上界；进一步推进了Wang和Zhu提出的完备染色猜想，即证明了最大度为7的平面图是完备10可染的；同时也证明了最大度为7的平面图是边面8-可染的；将平面图的结论推广到更复杂的图类上，证明了最大度至少为6的环面图的完备色数为∆+4，而最大度至多为5的环面图的完备色数为∆+5。此外，还证明了最大度至少为9的平面图的线性2-荫度至多为∆-1；以及证明了每个1-平面图的线性2-荫度至多为⌈(∆+1)/2⌉+14，且给出了1-平面图的一个轻边结构引理，证明了最小度至少为2的1-平面图要么包含一条29轻边，要么包含一个2-交错圈。三年内共发表与基金相关且挂有基金号的学术论文12篇，其中SCI检索9篇。