图的L(p,1)-标号和r-动态染色问题的研究

Graph coloring and labeling problems are important reasearch directions in graph theory. We shall study these problems by the Combinatorial Nullstellensatz Theorem, discharging method, probabilistic method, decomposition of graphs and other tricks. By investigating the structural properties of planar graphs and sparse graphs under some restricted conditions, we shall study the upper bound of chromatic number related such colorings. We shall study the upper bound of the L(2,1)-labeling number of graphs related to Griggs-Yeh conjecture, the 2-distance chromatic number (∆-dynamic chromatic number) of planar graphs related to Wegner-conjecture, the (list) r-dynamic coloring of plane graphs and sparse graphs related to r-dynamic conjecture proposed by Lai and et al. Furthermore, the computational complexity is further analyzed. Problems studied in this project are proposed and studied by famous international scholars. Therefore, the research of this project is of great importance.

图的染色与标号问题是图论研究中的重要方向。本项目主要运用组合零点定理、权转移方法、概率方法并结合图的分解展开研究。通过研究在部分限定条件下平面图、稀疏图的结构性质，探讨某些图类相关染色数的上界。主要研究内容有：围绕Griggs-Yeh猜想研究平面图在限定条件下的（列表）L(2,1)-标号数的上界；围绕Wegner猜想研究平面图的（列表）2-距离染色数（即∆-动态染色数）的上界并探讨相关算法的复杂性问题；围绕赖虹建等人提出的关于r-动态染色的猜想研究平面图和稀疏图的（列表）r-动态染色数。本项目所研究的问题都是国际著名学者提出的重要问题，因此，本项目的研究是有意义的。

图的染色与标号问题是图论研究中的重要方向。本项目主要运用组合零点定理、权转移方法和概率方法展开研究。通过研究在部分限定条件下平面图和稀疏图的结构性质，探讨某些图类相关染色数和标号数的上界。主要研究内容和结果有：围绕Griggs-Yeh猜想研究平面图在限定条件下的列表L(2,1)-标号数，给出了列表L(2,1)-标号数上界至多为Δ+3的3个充分条件；围绕Wegner猜想研究平面图的2-距离染色数（即Δ-动态染色数），证明了最大度至少为3的平面图的2-距离染色数至多为5Δ-7；围绕赖虹建等人提出的关于r-动态染色的猜想研究平面图和稀疏图的（列表）r-动态染色数，改进了最大度为7和8的平面图的r-动态染色数。此外，本项目还研究了图的单射染色、单射边染色和无圈边染色。本项目所研究的问题大部分是国际著名学者提出的重要问题，因此，本项目的研究是有意义的。本项目共完成论文12篇，其中发表期刊论文6篇，录用2篇，发表会议论文4篇。12篇论文中SCI收录4篇，EI收录4篇，一级期刊2篇，核心期刊2篇，圆满完成了项目预定的研究任务。