图的距离边着色问题

The edge-coloring with distance conditions of a graph, which was motivated by the frequency assignment problem, is a kind of generalized classical coloring of a graph. Because of its theoretical significance and application background, it is a popular research problem in many research fields, such as engineering, computer and mathematics. This project aims to adopt the methods of theory analysis and numerical experiment, and focuses on the following two problems. First, let j and k be two nonnegative integers and we consider the problem of L(j,k)-edge-labeling, in special the case of j≤k. Second, the strong edge-coloring is a special case of edge-labeling with distance condictions. If the channel resource is limited in a frequency assignment problem and one cannot get a good strong edge-coloring, then some kinds of appropriate relaxation is necessary in the coloring of edges. We will design the feasible relaxation methods, study the rules which the relaxation shows on some kinds of graphs and provide the theory basis for practical application. This project tries to analyze the structure characteristics reflected on the graph, and then to solve the preceding problems or design an effective algorithm to get a good upper bound for the corresponding edge-coloring. Also, this project tries to explore the effective methods for solving the problem of relaxed strong edge-coloring. This project will contribute to the graph coloring theory and explore the new research field for distance coloring in practical application. So, it is of great theoretical and application background. Moreover, The research results will enrich the present theory of L(j,k)-edge-labeling and provide the new theoretical basis for further study of edge-coloring with distance conditions.

图的距离边着色是经典边着色问题的推广，在频道分配问题中有着很重要的实际应用，受到了工程、计算机、数学等领域学者们的高度关注。本项目旨在采用理论分析和数值实验的方法，重点研究如下内容:（1）设j,k为两个正整数，我们将对图的L(j,k)-边标号问题进行研究，尤其是j≤k时的情形；（2）图的强边着色是一类特殊的距离边着色，当频道资源不足时，对应的着色方案要求对颜色分配的约束条件进行放松，我们拟设计可行的放松方案并深入研究它们在各种图类上表现出的规律，为实际应用提供依据。本项目力求通过分析上述问题在图上反映的结构特征，来求解得到边色数或者设计有效算法来求得边色数一个好的上界，并探索解决放松强边着色问题的有效方法。本项目的研究将为图的着色理论开辟新的研究方向，具有重要理论意义和应用前景；研究的成果将丰富L(j,k)-边标号的现有理论，为距离边着色的进一步研究提供新的理论基础。

图的着色问题起源于地图着色，是当代图论研究的前言课题之一，在频道分配、交通网络等方面有着广泛的应用。本项目对于放松的距离圆着色和距离边着色等问题进入了深入系统的研究，在几个关键性问题上取得到实质性进展。（1）研究了距离圆着色，提出放松d-距离圆着色的概念，并得到了放松2-距离圆着色问题的复杂度结论、外平面的放松2-距离圆着色色数，这些结果已经在杂志 Bulletin of the Malaysian Mathematical Sciences Society上在线发表。（2）研究了一些和放松距离边着色相关的问题，考虑了平面图、外平面图以及稀疏图的放松2-距离边着色及放松强边着色，得到的相关结论还不够完善，正在整理和进一步研究中。（3）研究了与边着色相关的算法，指导了一位本科学生在其毕业设计中研究了图的边着色问题，将二部图的边着色转化为一种矩阵形式，根据这个变形设计了一个求解二部图边着色的算法，并编程进行了实现。在此基础上，进一步研究了放松距离边着色的复杂度及近似算法，但由于该问题的已有结论较少，还处于探索阶段。（4）协助指导所在单位课题组的两名博士研究生，他们分别研究了社交网络的迭代定价问题和3-路的匹配问题，这两个问题都和图的着色问题相关联，所得的结果已经完成投稿。以上研究结果推动了相关着色问题的研究，具有重要的理论意义。