图的松弛染色问题

Many resource allocation problems can be modeled as graph coloring problems. Along with the developments of technologies and engineering methods,the corresponding graph coloring problems should also be improved from time to time. Some kind of relaxation to a graph coloring is a natural way to make this change.The relaxed graph coloring problem has very important applications in resource allocation problems such as channel assignment problem.The research in relaxed coloring problems has not yet been a hot point in graph theory. By developing new concepts and methods, this project aims to solve some important problems or conjectures concerning the upper bound of the relaxed L(j,k)-labeling, the Brooks type bound for the d-relaxed chromatic number and equitable d-relaxed coloring etc. This project provides new research directions in the field of graph coloring, and the research results will make a great contribution to graph coloring theory and provide more mathematical models and algorithms for practical problems.

许多资源分配问题可以抽象为图的某种染色问题。当工程技术手段和工作模式随着科技的进步而改进的时候，资源分配问题所对应的染色模型也应作相应改进。对图染色进行某种形式的松弛就是其中一种很重要的改进方法。松弛染色在频道分配等资源分配问题中有非常重要的应用。目前有关松弛染色方面的许多重要问题还没有得到充分研究。本课题拟通过发展新的概念和方法，围绕松弛L(j,k)-标号的上界、t-松弛染色数的Brooks型上界以及均匀t-松弛色数等方面的内容，对松弛染色的基本性质和重点问题进行系统研究，期望解决其中某些重要问题或猜想，促进松弛染色问题进一步的研究。本课题的研究结果是对经典染色理论和方法的深化和发展，有非常重要的理论意义，同时也为染色理论在频道分配等实际问题中的应用提供更坚实的理论基础、更贴近实际的数学模型以及更有效的算法。

资源分配问题可以抽象为图的某种染色问题。当工程技术手段和工作模式随着科技的进步而改进的时候，资源分配问题所对应的染色模型也应作相应改进。对图染色进行某种形式的松弛就是其中一种很重要的改进方法。松弛染色在频道分配等资源分配问题中有非常重要的应用。..本项目研究与频道分配问题相关的染色标号以及其他相关问题。对t-松弛染色数的基本性质进行研究，确定某些特殊图类的t-松弛染色数，对一些图类设计算法求解最优或较优t-松弛染。提出并研究松弛2-距离染色问题和松弛2-距离圆染色问题，证明问题的复杂度，对一些情形设计多项式时间算法，同时提出了该方向值得进一步研究的若干问题。为了解决一个基站同时使用多个频道的问题，我们还研究了图的n-重t-分离的多距离标号问题，得到了三角形和四边形网格图的n-重t-分离的L(j,j,…,j)-标号最优标号方案，为频道分配的实践提供参考。2014年Cao等提出网络上的时尚博弈问题，我们在Cao等人工作的基础上进一步推广其博弈均衡的概念，提出图上的时尚博弈效用问题。对该问题的复杂度进行了证明，确定一些图类的效用值，设计确定某些图类效用值的算法等。我们建立了rebel图的时尚博弈效用问题与图的松弛染色之间的关系，提出与这个方向相关的许多重要研究课题。我们对树图的任意星填装问题设计了一个线性时间算法，对另外两个特定星填装问题设计了近似算法。解决了一个与3-路填装相关的公开问题，证明了在三正则无爪图上最大3-路填装问题是NP-难的，为三正则无爪图设计了高近似比的最大3-路填装近似算法。..本项目通过发展新的概念和方法，对松弛染色的基本性质和重点问题进行了系统研究，得到了一些有重要意义的理论结果和有应用前景的算法，提出了许多非常有价值的新课题，深化和发展了经典染色理论和方法，为染色理论在频道分配等实际问题中的应用提供更坚实的理论基础、更贴近实际的数学模型以及更有效的算法。