有约束条件的图染色问题研究

Graph coloring is an important branch of graph theory, which are of wide applications in computer science, information science, management science and other fields. This direction has attracted considerable attention in the latest decades. In this project, we study the structural properties of graphs and various restrained coloring problems (e.g., acyclic coloring, list coloring, adjacent vertex distinguishing coloring). We try to solve the Borodin's conjecture, which says that planar graphs are acyclically 5-choosable. Aiming at the Alon-Sudakov-Zake conjecture, we will improve the known upper bound of acyclic edge chromatic number for a general graph and extend the new classes of graphs satisfying this conjecture. In order to investigate the adjacent vertex distinguishing coloring of graphs, we attempt to cut down the known upper bounds of the adjacent vertex distinguishing edge chromatic number and total chromatic number for a general graph and to characterize these two parameters for planar graphs of high girth. Moreover, we also will study some related problems such as domination number of graphs, energy of graphs, embedding of path or cycle for some classical networks, etc. At least 30 papers are completed after the project is finished, where at least 20 papers are indexed by SCI.

图的染色是图论研究的重要内容,在现代计算机科学、信息科学、管理科学等领域有着十分广泛的应用，一直得到国内外同行的极大关注。本项目从图的结构性质入手，研究图的各种约束染色问题，如无圈点染色、无圈边染色、线性染色、列表染色、邻点区别边染色、邻点区别全染色等。力争解决或部分解决Borodin等人提出的关于平面图是无圈5-可选的猜想；围绕Alon-Sudakov-Zaks猜想，对一般图改进已知无圈边色数的上界，找到新的图类满足该猜想。特别地，力争给出平面图的无圈边色数紧的上界，刻画有大围长的平面图的无圈边色数。研究图的邻点可区别边染色和全染色，改进一般图邻点可区别边色数和全色数的上界，并对最大度较大的平面图刻画这两个参数。此外，研究图的控制数、图的能量、一些著名网络图的路和圈的嵌入问题等，争取改进已有的结果。拟在四年内完成学术论文30余篇，其中20以上发表在SCI杂志上。

图的染色是图论研究的重要内容,在现代计算机科学、信息科学、管理科学等领域有着十分广泛的应用，一直得到国内外同行的极大关注。本项目从图的结构性质入手，研究图的各种染色问题（邻点区别边染色、邻点区别全染色、无圈染色、列表染色等）。部分解决了Borodin等人提出的关于平面图是无圈5-可选的猜想。找到了新的图类满足Alon-Sudakov-Zaks关于无圈边染色的猜想，建立了平面图的无圈边色数紧的上界，刻画了围长较大的平面图的无圈边色数。改进了一般图邻点区别边色数和全色数的上界，并对高度平面图确定了这两个参数。证明了平面图是3-好的和有向平面图是2-好的。研究树和哈林图的L(2,1)-标号与(2,1)-全标号，改进了一些已有结果。此外，研究图的荫度、控制数、图的能量、经典网络图的路和圈的嵌入问题等。四年内发表学术论文85篇，其中被SCI检索63篇。