图的边染色与星边染色及其相关专题

图的染色及其相关问题一直是图论研究的主线，在信息科学、计算机科学、经济学、社会学、工业生产与企业管理和现代军事指挥等诸多领域中都有着广泛而深刻的应用，得到了国际数学界和理论计算机科学界的广泛关注。本项目拟重点研究曲面上图的经典边染色和图的星边染色。给出具有较大Euler特征的曲面Σ上所有第二类图的最大度的最大值Δ(Σ)的精确值；给出一般曲面上第二类图的最大度的一个好的上界，进而给出Δ(Σ)的精确值；改进平面图、外平面图和最大度为4的图的星边染色数的上界，并推广到列表染色上去；证明外平面图的星边染色数不大于3Δ/2+1；证明最大度为3的图的星边染色数不大于6；改进k-退化图和稀疏图的列表星边染色数的上界；研究一些图类的星边染色数和列表星边染色数之间的关系。希望通过本项目的研究，解决一些相关问题与猜想，并以此丰富图的染色理论，推动图的染色理论乃至图论的研究与发展。

Graph coloring and its related problems have always been in the main line of graph theory. It has been widely and deeply applied in many fields such as information science, computer science, economics, sociology, industrial production and management, and modern military. It has received extensive attention from the international communities in mathematics and theoretical computer science. This project will focus on the classical edge coloring of graphs on surfaces and star edge coloring. We propose to find the exact values Δ(Σ) the maximum value of the maximum degree of class two graphs on given surfaces Σ with large Euler characteristic, present nice upper bounds for Δ(Σ) for general surfaces and eventually find the exact values for Δ(Σ) for all surfaces. For star edge coloring, we propose to improve the upper bounds for the star edge chromatic number of planar graphs, outer planar graphs, graphs with maximum degree 4 and extend those results to list star edge coloring. We also propose to confirm the outer planar graph conjecture and the conjecture on star edge chromatic numbers of graphs with maximum degree 3, improve the bounds for the list star edge chromatic number of k-degenerate graphs and sparse graph, and study the relation between the star edge chromatic number and its list chromatic number. This project will help solve some related problems and conjectures, to enrich the graph coloring theory, and to promote the research in graph coloring and even graph theory.