图的距离染色及其相关问题的研究

Graph coloring originated in the Four-Color Conjecture. It has become an important branch of graph theory due to its theoretical significance and its essential role in the applied science. This program will center on distance coloring, acyclic coloring and dynamic coloring of graphs..About distance coloring of graphs, we study Wegner’s conjecture (1977) on 2-distance coloring of planar graphs, and prove the conjecture for the graph with small maximum degree, and improve the known upper bound for the graphs with large maximum degree, and give some sufficient conditions that the conjecture holds. About r-distance coloring of graphs, we study the existence of the graph whose r-distance chromatic number is M and prove that there does not exist such graph and solve this problem completely. About acyclic coloring of graphs, the study mainly focuses on the graphs with maximum degree six. We improve the known result and prove that the graphs with maximum degree six are acyclically 7-colorable. About dynamic coloring of graphs, we study the classification of connected simple graphs on the sense of dynamic coloring and characterize the graphs in each Si (i=1, 2, 3, 4), and improve the known upper bound of the dynamic chromatic number of graphs, and additionally prove Reed’s (1998) conjecture about the upper bound of chromatic number of graphs.

图的点染色起源于重要的四色猜想。由于它的重要的理论意义和广泛的应用背景，现已发展成为图论的一个重要分支。本项目的研究主要围绕图的距离染色、无圈染色和动态染色这三种特殊的点染色展开。.关于图的距离染色，研究Wegner（1977）的关于平面图的2-距离色数的猜想，证明当最大度较小时猜想成立，当最大度较大时改进现有的上界，并给出猜想成立的一些充分条件。关于图的γ-距离染色，证明不存在γ-距离色数为M的图，彻底解决关于这种图的存在性问题的研究。关于无圈染色，主要研究最大度是6的图，改进已有的结果，证明最大度是6的图都是无圈7-可染的。关于图的动态染色，研究动态染色意义下图的分类问题，刻画出每一类图的特征；改进现有的动态色数的上界，进而证明Reed（1998）的关于图的色数的猜想成立。

起源于四色猜想的图的染色理论是图论的重要研究分支，具有重要的理论价值和应用背景。在国家自然基金项目(No.11771443)的资助下，本项目主持人和项目组成员的研究工作主要围绕项目申请书拟研究的图的距离染色、图的动态染色和r-hued染色、图的无圈点染色等展开。主要结果如下：.1、证明了最大度△≤5的平面图G的2-距离色数χ2(G)≤19, 改进了已有结果χ2(G)≤.20，这一结果离Wegner于1977提出的关于平面图的2-距离色数的上界的猜想更近了一步。证明了围长g(G)≥5而且最大度△≥40的平面图是(△+ 4)-2-距离可选的，从而给出了上述猜想成立的一个充分条件。证明了不含4,5-圈的平面图是max{29，△+3}-2-距离可选的。并且给出了围长是6的平面图其2-距离列表色数是△+2，从而表明上界是几乎可达的，同时也给出了上述猜想成立的又一充分条件。.2、给出了平均度较小的图以及平面图的r-hued色数的一些上界。证明了不含4-圈的平面图.的列表r-hued 色数≤r+8，其中r是一个正整数且r≥32。这一研究成果蕴含着对于最大度△≥26且不含4-圈的平面图Wagner的猜想成立。对于7 ≥ r ≥ 3，证明了围长至少是5的平面图的r-hued色数≤r+11. 推广一系列关于r-hued色数的结果.3、证明了当最大度 Δ(G) ≤ 6时，图G的无圈色数a(G) ≤ 9，改进了已有结果。证明了当最.大度 Δ(G) ≤ 7时，图G的无圈色数a(G) ≤ 12，改进了已有结果。.4. 研究了一般图的无圈全染色问题，证明了如果∆(G)≤5, 则存在一个常数c>0使得如果 g(G) ≥(c∆/r)log(∆2/r), 则χ＇＇a(G) ≤ ∆+r+2..5、研究了树的离心距离和EDS，得到了给定最大度或度序列的具有最小EDS的树。.6、其他相关专题：.研究了图的无圈列表染色、无圈列表边染色、IC-可平面图的邻和可区别全染色、平面图的DP-染色、图的强边色数、图的Laplacian谱、图的度量维数、平面图的列表L(p,q)-标号数、图的超欧拉性、图的Antimagic标号、图是哈密顿连通性、r-uniform 超图等专题，得到一系列有意义的结果。