图的多彩染色研究

Graph coloring has been an important branch of graph theory, which are of wide applications in information science, management science, computer science and other fields. It has been attracted considerable attention in the latest decades. The r-hued coloring of graphs is a new coloring which is stronger than the normal coloring but weaker than the coloring of square graphs. Based on precious results in the literature, we mainly analyze the structures of counterexample to the problems under consideration and apply the discharging method to study the r-hued coloring, acyclic r-hued coloring and linear r-hued coloring of graphs. We mainly investigate the following problems (1) Trying to improve the known upper bounds of the r-hued chromatic number. In order to investigate the Lai’s conjecture of r-hued chromatic number, we will explore the 3-hued chromatic number of plane graphs. (2) Aiming at the Montgomery’s conjecture, we will apply Probabilistic Method to find more sufficient conditions satisfying the conjecture. (3) Also we will characterize the acyclic (linear) r-hued chromatic number of special plane graphs, such as outer plane graphs, series-parallel graphs and Halin graphs. Moreover, we will explore the relation between the r-hued chromatic number and other parameters of graphs.

图的染色是图论研究的重要内容，在信息学、管理学、计算机科学等领域有着广泛的应用，是近年来的热点课题之一。图的多彩染色是比正常点染色强但比平方图的正常点染色弱的一种新染色。在前人研究的基础上，本项目从图的结构性质入手，对问题的极小反例进行深刻分析，运用权转移方法研究图的多彩色数、无圈多彩色数、线性多彩色数，以及这些参数之间的内在联系。主要研究如下几个问题（1）改进已知一般图的多彩色数的上界，针对Lai等提出的平面图多彩色数猜想，着重研究平面图的3-多彩色数；（2）围绕Montgomery猜想，运用概率方法找出更多使得该猜想成立的充分条件；（3）刻画外可平面图、系列平行图、Halin图等特殊平面图的无圈（线性）多彩色数。此外，我们也将积极探索图的多彩色数与图的其他参数之间的联系。

本项目遵照计划书执行，基本完成了预期目标。研究成果如下：一、刻画了树的线性多彩色数和圈、完全二部图、完全多部图等特殊图类的线性多彩列表色数，推广了现有的线性色数和多彩色数；此外还得到了具有较小最大度的图的线性2多彩色数的上界。二、不含K4子式图是一类非常重要的图类，研究该图类的色数具有很重要的理论意义，我们得到了不含K4子式图线性多彩色列表色数的上界，并且得到了平面图的线性2-多彩列表色数，推广了平面图的线性染色的结果；三、最大平均度是刻画图的稀疏程度的一个参数，我们研究了最大平均度有界的图的线性多彩列表色数，得到了三个相应的结果。