几类图的结构与染色问题

The structures and colorings of graphs is a basic but important branch of Graph Theory with rich theoretical results and broad practical applications. In this project we are about to investigate, based on some classic conjectures on Graph Theory, the structures and colorings of 1-planar graphs, (d,1)-planar graphs, IC-planar graphs, psuedo-outerplanar graphs, IC-outerplanar graphs and double-outerplanar graphs, by proper mathematical mathods and tools such as discharging mathod, probabilistic mathod, programming theory and so on. The contents consist of the research on the existence of light subgraphs, minor theory, the testing algorithms and the edge colorings, total colorings, list edge (total) colorings, acyclic vertex (edge) colorings, equitable vertex colorings, incident colorings and game colorings of those families of graphs. We aim to solve or partially solve some related famous problems or conjectures when they are restricted to 1-planar graphs or its sub-families, and to explore the applications of the structures and colorings of those mentioned topological graphs. In particular, we will firstly introduce the notions of (d,1)-planar graphs, IC-outerplanar graphs and double-outerplanar graphs in this projrct, and then do some original theoretical reseach on the structures and colorings of those families of graphs. This project is related to the field of Graph Theory, Programming Theorey, Probalility Theory and Combinatorial Topology. It would promote the development of Theoretical Computer Science and Graph Theory once we have settled centain problems.

图的结构与染色问题是图论中基础而重要的研究方向，其具有众多的理论成果和广泛的应用背景。本项目围绕图论中几个经典的猜想，利用权转移方法、概率方法等数学方法与规划论等数学工具研究1-平面图、(d,1)-平面图、IC-平面图、伪外平面图、IC-外平面图与双外平面图等几类图的结构与染色问题,其中包括它们的轻子图的存在性、子式理论、判定算法以及边染色、全染色、列表边（或全）染色、无圈点（或边）染色、均匀点染色、关联染色与博弈染色等，力求在1-平面图及其子类的层面上解决或部分解决上述研究领域中的难题或猜想，并探索上述几类拓扑图的结构与染色问题在现实生活中的应用价值。此外，上面提及的(d,1)-平面图、IC-外平面图与双外平面图是本项目首次提出的，这里将对其做开创性的理论研究。本项目涉及到图论，规划论，概率论，组合拓扑等众多数学领域，问题的解决对理论计算机科学与图论的理论发展有着较大的促进作用。

图的结构与染色问题是图论中基础而重要的研究方向，其具有众多的理论成果和广泛的应用背景。本项目主要对于1-平面图及其几个重要子类，如NIC-平面图、IC-平面图、平面图与外1-平面图等的结构与染色问题做具体的研究。在结构方面，主要研究特定图类中的轻子图的存在性，以及在某种染色意义下的可约结构的存在性，证明了最小度至少为6的1-平面图、最小度至少为5且最小边度至少为12的1-平面图、最小度至少为5的NIC-平面图都含有一个轻3-圈，并给出了它的height与weight值的较好的上界，同时给出了NIC-平面的完全多部图与IC-平面的完全多部图的完整刻画。在染色方面，主要是围绕染色图论中的一些经典的定理与猜想，如边染色Vizing定理、全染色猜想、列表染色猜想、全标号猜想等，确定图的相关染色参数的（相对较好的）上界，或者验证相关猜想。例如，本项目给出了外1-平面图具有第一类边色数的充分必要条件，以及最大度为8的平面图的全色数是9的一些充分条件，证明了全染色猜想对于外1-平面图成立并给出了外1-平面图具有第一类全色数的几个充分条件，证明了列表染色猜想对于最大度至少为5的外1-平面图与最大度至少为8且不含相邻的4-圈的平面图成立，证明了(2,1)-全标号猜想对于最大度至少为12的平面图成立，提出了群边染色的概念以及群边染色猜想并对于围长至少为4Δ/(Δ-2)的平面图证明了该猜想。本项目的另一个研究主题是图的均匀点染色。首先，围绕均匀正常点染色方面的两个著名猜想：均匀Δ-染色猜想与Chen-Lih-Wu猜想，本项目对于1-平面图及其子类的均匀染色数与均匀染色阀值做系统的研究，证明了上述两个猜想对于最大度至少为15、13、12、3的1-平面图、NIC-平面图、IC-平面图、外1-平面图成立。除此之外，本项目对于图的r-均匀正常点染色也做了一定的研究，得到了一些有意义的结论。另一方面，本项目围绕图的均匀点荫度猜想，得到了一些图类的均匀点荫度的好的上界，证明了均匀点荫度猜想对于最大度至少为|G|/2的图或者最大度至多为3的图成立，给出了平面图的均匀点荫度至多为3的充分条件，提出了均匀列表点荫度猜想，并证明了该猜想对于最大度至少为8的平面图成立。本项目涉及到图论，规划论，概率论，组合拓扑等众多数学领域，问题的解决对理论计算机科学与图论的理论发展有着较大的促进作用。