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

项目名称： 图的无圈染色和邻点可区别染色

项目编号： No.11301035

项目类型： 青年科学基金项目

立项/批准年度： 2014

项目学科： 数理科学和化学

项目作者： 王艺桥

作者单位： 北京中医药大学

项目金额： 22万元

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

中文关键词： 无圈染色；线性荫度；点可区别染色；边-面染色；完备染色

英文摘要： 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

英文关键词： acyclic edge coloring；linear k-arboricity；adjacent vertex distinguishing coloring；edge-face coloring；entirely coloring