图染色及标号中的若干问题

Coloring and labeling of graphs are important directions in graph theory. This project aims at studying some important graph coloring and labeling problems by using discharging method, probabilistic method, the Combinatorial Nullstellensatz Theorem and polynomial theory. More specifically, we shall study coloring and labeling of surface graphs and plane graphs by investigating their structural properties under some restricted conditions as follows: L(1,1)-labeling of graphs related to Wegner-conjecture, r-dynamic (list) coloring of graphs, injective-(list) coloring of plane graphs related to Luzar-conjecture, and strong-edge (list) coloring of plane graph related to the strong-edge conjecture. Furthermore, we shall also study BB-(list) coloring, on-line list coloring and some other related colorings of graphs. Most of the problems discussed here are proposed and studied by noted researchers, some of them are also proposed by ourselves. The research in this project is of great importance.

图的染色及标号问题是图论研究中一个重要的方向。本项目主要应用Discharging方法、概率方法、组合零点定理、多项式理论并结合图的分解围绕图的染色及标号问题中的若干重要问题展开理论研究。通过研究在部分限定条件下曲面图、平面图的结构性质，探讨这些图类相关染色及标号问题。主要研究内容有：围绕Wegner-猜想，研究图的L(1,1)-标号和r-dynamic(列表)染色；围绕Lužar-猜想，研究平面图的Injective-(列表)染色；围绕强边染色猜想，研究图的强边(列表)染色等，探讨若干重要图类的BB-(列表)染色、在线列表染色和相关染色的算法复杂性问题。本项目所研究的问题大部分是国际著名学者提出的一些重要问题，部分问题由我们首次提出，因此，本项目的研究是十分有意义的。

本项目主要应用图的结构理论、组合理论和多项式理论，同时结合图的定向方法，通过引入复变量多项式，应用Alon-Tarsi有关图的列表染色与多项式相关的经典定理（包括零点组合定理）探索相关染色问题中临界图的结构性质展开相关染色问题的研究。围绕Lužar-猜想研究平面图和稀疏图的（列表）injective-染色，主要研究平面图在最大度、围长等限定条件下，（列表） injective-色数关于最大度的线性函数式作为其上界，逐步逼近该猜想的正确性，特别获得了平面图G的injective-边色数至多为Δ+1若干充分条件。围绕Wegner-猜想研究关于平面图的L(p,q)-标号及（列表）2-距离染色，获得了若干图的L(1,1)-标号数的上界。特别对于围长至少为5的平面图G和满足 2≤c≤6的整数c，讨论最小正整数M(c) ,使Δ(G)≥M(c)时，有2距离染色数至多为Δ+c。在本项目中我们证明了M(6)≤12 。围绕赖虹建等学者提出的有关r-dynamic染色猜想展开研究，获得了若干图的（列表）r-dynamic染色数的上界。特别对平面图，我们获得了（列表）r-dynamic 色数恰为r+1的图类和至多为r+2的图类若干充分条件，也获得了部分稀疏图的列表r-dynamic染色数恰为r+1的若干充分条件。对于社交网络在超图中的社会影响力最大化问题方面，主要研究了其相关算法及模型。基于Ramannujian随机图路径问题的密码哈希函数的设计，以及基于图染色问题的密码体制的研制等，探讨了网络安全及网络密码中的一些重大问题。. 本项目所得结果改进了前人的一些工作，推进了一些著名猜想的发展，丰富了图染色和标号理论。至今完成学术论文40多篇，目前在一些国内外本领域重要学术期刊正式发表30篇，会议论文3篇，在国际著名出版社Springer出版学术专著一部，获浙江省于2019年首次设立且当年唯一的一个国际科学技术合作奖。培养博士及硕士研究生20名，圆满完成了本课题所预定的研究任务。