图的邻点及邻和可区别染色研究

Graph coloring has an important position in graph theory. It has been applied very widely in many fields such as physics, chemistry, computer science, network theory, and so on. Moreover, it has attracted great attention at home and abroad. The neighbor distinguishing coloring and neighbor sum distinguishing coloring of graphs are the research hotspots in graph theory in recent years. In this project, we will study the structural properties of graphs and four coloring problems, that is, neighbor distinguishing edge coloring, neighbor distinguishing total coloring, neighbor sum distinguishing edge coloring and neighbor sum distinguishing total coloring. By using the Discharging method, the Combinatorial Nullstellensatz and MATLAB, we will start our research from the following three aspects: Firstly, we will investigate the relationship between the corresponding chromatic numbers of the above four colorings and some other graph invariants and improve the known upper bounds for general graphs. Secondly, we will develop the new classes of planar graphs satisfying the corresponding conjectures of the above four colorings. Finally, we will try to characterize the corresponding chromatic numbers of the above four colorings of planar graphs with large maximum degree. Solution of these problems will greatly enrich the research results of related topics and have important theoretical significance. At least 10 papers will be completed after the project is finished, where at least 5 are indexed by SCI.

图的染色是图论研究中的一个重要的研究方向，在物理、化学、计算机科学、网络理论等诸多领域有着十分广泛的应用，一直得到国内外同行的极大关注。图的邻点可区别染色和邻和可区别染色是近几年来图论界的研究热点。本项目从图的结构性质入手，利用权转移、组合零点定理等方法，结合MATLAB计算，着重研究图的邻点可区别边染色、邻点可区别全染色、邻和可区别边染色和邻和可区别全染色，从以下三个方面进行展开：(1) 探讨每个相应色数与其他图参数之间的关系，对一般图改进其已有结果的上界；(2) 找到更多的平面图满足每个相应的猜想；(3) 刻画最大度较大时的平面图的每个相应色数。本项目所研究问题的解决，将会极大地丰富相关课题的研究成果，具有重要的理论意义。拟在3年内完成学术论文10篇左右，其中半数以上发表在被SCI检索的杂志上。

图的染色是图论研究和算法复杂性分析的重要内容，在物理、化学、计算机科学、网络理论等领域有着十分广泛的应用，得到国内外同行的极大关注。本项目从图的结构性质入手，研究图的邻点可区别边染色、邻点可区别全染色、邻点扩张和可区别全染色、边面全染色、强边染色等。给出了最大度△=6的图的邻点可区别边色数至多为12，刻画了最大度△≥13的平面图的邻点可区别边色数。证明了最大度△=9的平面图是12-邻点可区别全可染的，满足张忠辅等人提出的关于图的邻点可区别全染色猜想，刻画了最大度△≥11的平面图的邻点可区别全色数。证明了所有的Halin图的邻点扩张和可区别全色数不超过3，特别是对于最大度△=3的Halin图满足猜想。利用组合零点定理分别给出了最大度△≥6的Halin图的边面列表全色数和Subcubic环面图的列表强边色数的上界。立项以来，项目组成员在国内外学术刊物上发表论文8篇，其中被SCI检索5篇。