图的均匀染色及其相关问题的研究

The theory of equitable coloring of graphs is a basic and important research direction in graph theory. This project investigates the equitable vertex coloring of graphs around the equitable Δ-coloring conjecture and the Chen-Lih-Wu conjecture, while researching the equitable tree coloring of graphs around the equitable vertex arboricity conjecture and its relative conjectures, and strives to improve or perfect the previous classical results or obtains new results, so as to solve or partially solve some problems and conjectures in this field. Secondly, this project studies the r-equitable vertex (tree) coloring of graphs. In the course of this study, a new concept, named the chromatic (arboreal) evenness of a graph, is proposed and used to describe how equitable a vertex (tree) coloring of a graph is. This parameter is an innovation of this project, which allows the researchers to consider some problems and conjectures related to the equitable coloring of graphs from a new perspective, and may provide a new research program for settling some classic conjectures. Finally, this project studies the parameterized algorithms for the equitable coloring of graphs and its related problems for the purpose of revealing the computer solvability of the researching theoretical issues, and providing a theoretical and algorithmic support for its applications in some interdisciplinary research such as complex networks and bioinformatics.

图的均匀染色理论是图论中基础而又重要的研究方向。本项目首先围绕均匀Δ-染色猜想与Chen-Lih-Wu猜想研究图的均匀点染色，再围绕均匀点荫度猜想等相关猜想研究图的均匀树染色，力求改进或完善前人的经典结论，或得到新的结果，从而解决或基本解决该领域的若干难题与猜想。其次，本项目将研究图的r-均匀点（树）染色，并在研究的过程中提出图的点（树）染色均匀度这个新概念，用以刻画图的点（树）染色的均匀程度。该参数的提出是本项目的一个创新，它使研究者可以从新的角度考虑一些与图的均匀染色相关的问题与猜想，为经典猜想的最终解决提供新的研究方案。最后，本项目将研究图的均匀染色及其相关问题的参数算法理论，揭示所研究的理论问题的计算机可解性，为其在复杂网络和生物信息学等交叉学科的应用提供理论与算法支持。

图的均匀染色理论是图论中基础而又重要的研究方向。本项目主要围绕均匀Δ-染色猜想与Chen-Lih-Wu猜想研究图的均匀点染色，再围绕均匀点荫度猜想研究图的均匀树染色，改进或完善了前人的经典结论，得到了新的结果，从而解决或基本解决了该领域的若干难题与猜想。此外，本项目也研究了图的均匀边染色以及图的均匀退化染色，得到了一些漂亮的结果。最后，本项目研究了图的均匀染色及其相关问题的参数算法理论，揭示了所研究的理论问题的计算机可解性，为其在复杂网络和生物信息学等交叉学科的应用提供理论与算法支持。