可嵌入一般曲面的图的列表边染色与列表全染色研究

More than forty years ago, the list-edge coloring and the list-total coloring were posed by some famous experts of Graph Theory, Vizing, Erdös and Taylor etc. And then they have been attracting great attention of scholars both at home and abroad, and one of hot topics on Graph Theory. Our project intends to generalize the related results about the list-edge coloring and the list-total coloring of planar graphs to various classes of graphs embedded on general surfaces, such as chordal planar graphs with adjacent small-faces, the graphs with the relation between their maximum degree and Euler characteristic number of surfaces, and the graphs embedded on general surfaces (for example, the Torus, the Projective Plane, the Quadric Surface) etc. Firstly, we will depict more characters about the list critical graphs; secondly, we will identify their edge k-choosability and total (k+1)-choosability, and then determine their list edge chromatic numbers and the list total chromatic numbers or their tight bounds. Meanwhile, we will use the generalized Euler’s Formula, extend the classic Discharging Method of a planar graph, actively explore a novel method to construct the edge-face parameters, and first give their assistant programs and source codes with MATLAB. Therefore, the results of this project will enrich the graph coloring theory, and provide theoretical bases for the practical problems embedded on surfaces.

四十多年以来，由著名图论专家Vizing、Erdös、Taylor等所提出的图的列表边染色、列表全染色一直备受国内外学者的关注，是图论的热门研究课题之一。本项目拟将平面图的列表边染色与列表全染色问题的相关结论推广到可嵌入一般曲面的不同图类，如含有小面相邻的弦平面图、具有最大度与该曲面的欧拉示性数某关系式、可嵌入一般曲面(如环面、仿射平面、二次曲面)等。首先，刻画不同临界可选图的性质；其次，确定出这些图类的边k-可选性、全(k+1)-可选性，从而，确定出其列表边色数、列表全色数或紧的界。同时，应用广义的欧拉公式，推广经典的权值转移法，积极探索适用的边-面-参数构造法，并首次给出MATLAB辅助程序及其源代码。本项目研究结果将丰富图染色理论、为可嵌入曲面的实际问题提供理论基础。

染色理论是图论的重要分支，而图的列表染色问题属于图论研究的热点和难点。本项目围绕“可嵌入一般曲面的图的列表边染色与列表全染色”进行了研究，重点采用了“权值转移法、极图反例、染色独立集、最小特征值”等研究手段，部分解决了列表染色猜想1、列表染色猜想2，该问题的相关研究结果与方法不仅解释了不断涌现的许多新型实际问题，而且推动了图论的独立控制集、极图理论、谱理论等不同分支理论的发展。本项目共资助发表国际SCI期刊科研论文7篇。