图的线性荫度、均匀染色及其相关问题的研究

Graph coloring theory occupies an important position in the study of graph theory, and it has important applications in the optimization, computer theory, network design, etc. In this project we will research some classic problems of graph colorings: the linear arboricity, total coloring, equitable coloring and the extension of them: the linear k-arboricity, equitable vertex arboricity etc. Our aim is to determine the linear arboricity, total chromatic number, equitable chromatic number, equitable vertex arboricity of some large classes of graphs such as planar grpahs, graphs embedded in surfaces, solve or partly solve some related famous conjectures. This project mainly includes two parts, one part is the classic problems of graph coloring, the other part is the extension of them. The solutions of the problems in this project will promote the development of graph coloring.

图的染色理论在图论研究中占有重要的地位，在最优化、计算机理论、网络设计等方面都有着重要的应用。本项目计划研究几个经典的图的染色问题：线性荫度、全染色、均匀染色以及它们的推广：线性k-荫度，均匀点荫度等。我们力求确定一些大的图类，如平面图、可嵌入到曲面上的图的线性荫度，全色数，均匀色数，均匀点荫度等，解决或部分解决相关的几个著名猜想。本项目研究的内容主要包括两个部分：一部分是图论中经典的染色问题，另一部分是这几类经典染色问题的推广，问题的解决对于图的染色理论将有较大的促进作用。

图的染色理论在图论研究中占有重要的地位，在最优化、计算机理论、网络设计等方面都有着重要的应用。本项目旨在研究几类经典的染色问题：线性荫度、全染色、均匀染色以及它们的推广：线性k-荫度，均匀点荫度等，具体包括：1. 平面图、可嵌入到曲面上的图的线性荫度、线性k- 荫度； 2. 全染色猜想；3. 平面图、1-平面图、可嵌入到曲面上的图的均匀色数；4. 均匀点荫度猜想。.对于问题1，利用欧拉公式和权转移的方法给出了5-圈不与3-圈或4-圈相邻的平面图的线性2-荫度的一个较小的上界，4-圈不共点的平面图的线性2-荫度的一个上界，这两个结果都已经以论文的形式发表。另外对于不含有相交5-圈的平面图的线性2-荫度，也给出了它的一个较小的上界，这一结果已经投稿。.对于问题2，通过构造平面图的一些特殊结构，利用欧拉公式证明了如下图形的全色数等于Delta+1:（1）最大度Delta至少为7且不含有相邻5-圈的平面图，（2）最大度Delta至少为6且不含有相交4-圈和相交5-圈的平面图，（3）最大度Delta至少为6且不含有6-圈和相邻5-圈的平面图，（4）最大度Delta至少为8且不包含含有两条弦的相邻i-圈和j-圈，其中i,j属于{5,6,7}的平面图，（5）最大度Delta大于等于8的平面图且对于每一个顶点v都存在两个整数i,j属于{3,4,5,6,7}，使得v都不与相邻的i-圈和j-圈相关联。另外我们还证明了最大度Delta至少为8且不含有弦5-圈的平面图的列表边色数等于Delta，列表全色数等于Delta+1. 这些结果也都已经以论文的形式发表。.对于问题3，因为k-退化图和k-染色图之间的关系需要证明，而且研究均匀染色需要用到其中的一些结论，所以此问题还在进一步研究中。.对于问题4，吴建良等人在2013年提出了均匀点荫度猜想，即：任何简单图G的点集合都可以均匀的分成m个子集，并且每一个子集都是一个导出森林，其中Delta（G）表示图G最大度，m是一个整数，且满足$m\geq\lceil\frac{Delta+1}{2}\rceil$。我们证明了对于5-退化图，该猜想成立。该结果也已经以论文的形式发表。.此外我们还研究了1-2-3猜想和平面图、曲面图的列表单射染色，相关结果见发表的论文。