图的几类标号问题

With the rapid development of market economy and the radio communication, the conflict between the great demand for radio frequency and the limited frequency resource has taken place, so it is quite necessary to find the solution to assign frequency appropriately. As special colorings, distance two labeling and its generalizations emerged in this background，and they have gained much attention in the last decade. In this project, We will research some kinds of labeling for graphs, such as L(p,q)-labeling, (d,1)-total labeling, (d,1)-vertex-face total labeling and so on. The focus will be placed on the conjecture by Griggs and Yeh and the characterization of L(2,1)-labeling number for trees. For the conjecture on (d,1)-total labeling by Havet and Yu, we hope to find out more graphs satisfying the conjecture, and also the characterization for trees. We will systematically study (d,1)-vertex-face total labeling, and extend some results of vertex-face total coloring into it. Circular distance two labeling, acyclic edge coloring and adjacent vertex distinguishing total coloring are also our research subjects. We plan to publish 3-5 research papers with over half of them cited by SCI.

随着市场经济和无线通信事业的快速发展，无线电频率需求量的逐渐增大与有限的无线电频率资源之间的矛盾日益增大，使频率分配问题成为当前亟需解决的重要课题。图的距离2标号问题以及它的一些推广，就是在这种背景下产生的，它们可以看做是一些特殊的染色问题，近十年来受到了国内外同行的极大关注。本项目研究图的L(p,q)-标号、(d,1)-全标号、(d,1)-点面全标号等相关标号问题。围绕著名的Griggs和Yeh的猜想，重点开展对树图L(2,1)-标号数的刻画。致力于Havet和Yu关于图的(d,1)-全标号的猜想，力争能够寻找到更多的图类满足该猜想，并进一步研究树图(2,1)-全标号数的刻画条件。将系统地研究图的(d,1)-点面全标号，并推广点面全染色中的相关结果到(d,1)-点面全标号问题上。研究图距离2圆标号、无圈边染色、邻点可区别全染色等相关问题。拟在三年内完成3-5篇论文，半数以上被SCI收录。

随着社会的发展，无线电技术及其应用已成为人类生产生活中必不可少的一部分。所有的无线电业务都离不开无线电频率，但无线电频率资源却是有限的。因此，合理地分配无线电频率已经成为了亟待解决重要问题。在此应用背景下，图的L(2,1)-标号问题（即图的距离2问题）和它的一些推广成为了当前的热点。树型网络(树图)在网络拓扑结构中有着无可替代的地位，是中小型网络采用的主要拓扑结构，而树图的L(2,1)-标号数不是Δ+1就是Δ+2，因而寻找其刻画条件就变得非常有意义。自立项以来，本项目组致力于研究该课题的研究，完成了最大度为3的树的L(2,1)-标号数的刻画，该成果发表于杂志《数学学报（中文版）》。图的(2,1)-全标号问题是L(2,1)-标号问题的一个重要推广，树图在(2,1)-全标号下有着与L(2,1)-标号类似结论，其(2,1)-全标号数不是Δ+1就是Δ+2。本项目组定义了树图中坏点，证明了：对于最大度至少为9的树，若不存在距离为偶数的坏点，则其(2,1)-全标号数为Δ+1。此成果发表于杂志《Journal of Combinatorial Optimization》。本项目组还研究了距离2标号问题的另一种推广，图的(2,1)-点面标号问题，并取得如下成果：完全刻画了树、圈、欧拉二部图、四阶完全图的(2,1)-点面标号数；给出了外平面图(2,1)-点面标号数的紧的上下界；完全刻画了开外平面图以及至含有一个闭内面的外平面图的(2,1)-点面标号数。该系列成果发表于《浙江师范大学学报（自然科学版）》。此外，本项目还研究了图的无圈染色问题，改进了M. Montassier等学者的关于平面图是无圈4可选的一个充分条件。证明了不含相交的3、4 或5-圈的平面图是无圈4-可选的。本项目组共计发表相关论文9篇，其中5篇被SCI检索。本项目的取得的这些研究成果极大地丰富了图的标号及相关问题的研究内容。