图的无圈和广义无圈染色

The acyclic coloring of graph is a proper vertex coloring of the graph such that there is no cycle in the subgraph induced by the vertices of any two of the colors. The generalized acyclic coloring of graph is a generalization of acyclic coloring of graph, such as r-acyclic coloring, degenerating coloring, colorings with restrictions on the union of color classes and so on, the research on these kinds of colorings is a new trend in graph coloring theory. It has some theoretical significance to conduct research on these topics. However, at present, the research in this regard is far from enough. In this project, we will put these kinds of colorings into a same research system and conduct research on it by various probabilistic method, try to solve some conjectures and problems in this regard, such as acyclic edge coloring conjecture, degenerating coloring conjecture and so on. We know that the solutions to these conjectures have large role in promoting the development of graph coloring theory, laying a sound foundation for the further development of acyclic coloring and generalized acyclic coloring of graph, and promoting the complete solutions of the related conjectures and problems.

图的无圈染色是指图的正常点染色使得染有任意两种颜色的顶点的导出子图是森林，它是图的染色理论的经典研究内容，图的广义无圈染色是无圈染色概念的推广和一般化的图的染色问题，如r-无圈染色、退化染色、色集有限制的染色等，它们是图的染色理论的前沿研究课题。这些染色问题的研究对图的染色理论的发展有重要的理论意义，但目前对这些问题的研究还远远不够，尚存在许多没有解决的新问题和猜想。本项目将采用多种随机方法深入研究图的无圈和广义无圈染色问题，将图的无圈染色、r-无圈染色、退化染色、色集有限制的染色纳入到同一个系统中进行研究，拟解决或部分解决几个相关的猜想和问题，如无圈边染色猜想、退化染色猜想和几个相关的问题，并改进现有的染色数的上界。本项目的顺利实现将有效地促进图的染色理论的发展、丰富和完善图的无圈和广义无圈染色的研究内容和方法、为该研究的进一步发展奠定基础，并将有效推动相关的重要猜想和问题的彻底解决。

图的无圈染色是指图的正常点染色使得染有任意两种颜色的顶点的导出子图是森林，它是图的染色理论的经典研究内容，图的广义无圈染色是无圈染色概念的推广和一般化的图的无圈染色问题，如r-无圈染色、退化染色等，它们是图的染色理论的前沿研究课题和经典研究内容。本项目利用概率方法和结构图论的方法就图的无圈和广义无圈染色进行了深入的研究，获得了图的无圈和广义无圈染色问题的若干研究结果。具体研究内容和研究结果是：1.用 Entropy compression method将Borodin的关于平面图的退化染色的猜想放到一般图上来进行研究并改进了Mohar等人关于图的退化染色（广义无圈染色）的研究结果; 2. 应用Lopsided General Local Lemma 研究了有围长限制限制的条件下的r-无圈染色，将Greenhill等人的r-无圈染色的上界改到了关于最大度的线性函数；3. 综合应用多种概率方法首次找到了星边列表染色一个上界；4. 应用局部引理和改进的局部引理，两次改进了有围长限制的图的无圈染色数的上界。项目研究问题的较好解决，不仅为无圈和广义无圈染色的研究大大推进了一步，也为相关问题和猜想的解决或部分解决提供了较好的研究方法和思路。