图的无圈染色和邻点可区别染色

Graph coloring has been an important branch of graph theory research. In particular, it has attracted considerable attention in the latest decades.In this project, we will study the structural properties of graphs and various coloring problems (e.g., acyclic vertex coloring, acyclic edge coloring, adjacent-vertex-distinguishing edge coloring, adjacent-vertex-distinguishing total coloring, linear coloring ). Aiming at the Alon-Sudakov-Zake conjecture, we will improve the currently known upper bound of acyclic edge chromatic number for general graphs and develop the new classes of graphs satisfying this conjecture. We try to solve the Borodin's conjecture, which says that planar graphs are acyclically 5-choosable.In order to investigate the adjacent-vertex-distinguishing coloring of graphs, we will attempt to reduce the existed upper bounds of the adjacent-vertex-distinguishing edge chromatic number and total chromatic number for general gtaphs and to characterize these two parameters for planar graphs of high girth. Also we will discuss some related coloring problems such as linear coloring, 3-colorability and 3-chooability of planar graphs, edge-face coloring of plane graphs, etc. Moreover, we will explore actively the application of graph coloring result in life science, medical science, management science and other practical problems. At least ten papers are completed after the project is finished, where at least five are indexed by SCI.

图染色一直是图论研究的重要内容之一,近些年来更成为热点课题。本项目从图的结构性质入手，研究图的各种染色问题，如无圈点染色、无圈边染色、邻点可区别边染色、邻点可区别全染色、线性染色等。围绕Alon-Sudakov-Zaks猜想，对一般图改进已有的无圈边色数的上界，找到新的图类满足该猜想。特别地，力争给出平面图的无圈边色数紧的上界，刻画有大围长的平面图的无圈边色数。研究图的无圈点可选性，力争解决Borodin等提出的平面图是无圈5-可选的猜想。研究图的邻点可区别边染色和全染色，改进一般图邻点可区别边色数和全色数的上界，并对最大度较大的平面图刻画这两种参数。此外，研究图的线性染色、平面图的3-可染性和3-可选性、平面图的边面全染色等相关问题。我们也积极探索图的染色问题在生命科学、医学、管理科学等实际问题中的应用。拟在3年内完成学术论文10篇左右，其中半数以上发表在被SCI检索的杂志上。

图的染色是图论研究的重要内容，在现代计算机科学、信息科学等领域有着十分广泛的应用，一直得到国内外同行的极大关注。本项目从图的结构性质入手，研究图的各种染色问题，如无圈边染色、点可区别染色、平面图的各种全染色、线性染色、图的线性点荫度和线性边荫度等。围绕Alon-Sudakov-Zaks猜想，一个简单图G的无圈边色数a´(G)至多是△+2。我们证明了：若一个平面图G不含3-圈相邻于一个6-圈，则a´(G)≤△+2。找到了新的图类满足该猜想。此外，Basavaraju 等人证明了：最大度为4且非4-正则的图是无圈6-边可染的。通过引入新的换色技巧和细致的结构分析，我们进一步解决了4-正则的情形，即证明了：若G是一个4-正则图，则a´(G)≤6。在研究平面图的边-面染色和完备染色，我们得到了一些结果，较大程度地改进了前人的工作。具体如下：（1）证明了：每一个△=8的平面图也是(△+2)-完备可染的。 (2) 作为完备染色的加强与推广，我们考虑了平面图的列表完备染色。证明了：每一个△≥10的平面图是(△+2)-完备列表可染的。 (3)证明了: 每一个△≤5的平面是(△+5)-完备列表可染的。(4) 证明了：每一个最大度为6的平面图是8-边-面可染的。 (5)证明了: 每一个△≥9的平面图是(△+1)-边-面列表可染的。在图的点荫度领域我们得到了以下的几个结果： (1) 证明了：没有相交三角形的平面图的点荫度至多为2。这改进了一个已知结果：没有距离小于等于3的三角形对的平面图的点荫度至多为2。(2) 证明了：没有3-,5-圈相邻的可嵌入环面的图点荫度至多为2。(3) 证明了：没有3-,4-圈相邻的可嵌入环面的图点荫度至多为2。(4) 证明了：没有4-,5-圈相邻的可嵌入环面的图点荫度至多为2。关于图的线性2-荫度问题，我们证明了：每一个平面图G的线性2-荫度至多为 {(△+1)/2}+6.这以结果改进了Lih, Tong和Wang(2003)证明的：每一个平面图G的线性2-荫度至多为 {(△+1)/2}+12的结果. 我们还改进了Lih, Tong和Wang(2003)，Ma,Wu和Hu(2009)等人证明的结果：若一个平面图G不含3-圈正常相邻一个4-圈，则la_2(G) ≤{△/2}+5。立项以来，项目组成员在国内外学术刊物上发表SCI论文15篇。