图的标号及相关问题研究

Graph coloring, labeling and their applications are important research topics in graph theory. There are many challenging problems and has wide applications to network optimization, channel assignment, algorithm design and VLSI. This project studies graph coloring and labeling and their applications. Using discharging method and polynomial method, we shall analyse the structure of planar graph with forbidden cycle lengths and graphs of bounded maximum average degree, and study colorability and choosability of these graphs. We also study other graph coloring and labeling problems, including (m,d)*-coloring, BB-coloring, BB-list coloring, L(p,q)-labeling and game labeling of graphs. We aim to solve or partially solve Wegner's conjecture concerning L(1,1)-labeling of planar graphs, and Steinberg's conjecture concerning 3-colorability of planar graphs with forbidden short cycles. We use probabilistic method and polynomial method to study graphs with special properties and with given coloring and labeling parameters. We shall investigate the complexity of some coloring problems. Some of the problems in this proposal are raised by well-known mathematicians and some problems are raised by ourselves. The contents of these problems involve graph theory, combinatorial optimization and algorithmic complexity.

图的染色、标号及其应用一直是图论研究的重要内容之一，其研究富有挑战性，在网络优化、网络频率分配、算法设计和大规模集成电路设计等方面有重要应用。本项目主要研究图的染色理论、标号理论及图论在其它学科中的应用等问题。应用权转移技术和多项式理论研究在平均度或短圈限定条件下平面图的结构性质，从而探讨这些图类的3-可染（可选）问题及形如(m,d)*-（列表）染色、BB-（列表）染色、 L(p,q)-标号、对局标号等，以解决或部分解决Wegner关于平面图的L(1,1)-猜想和Steinberg 关于3-染色猜想为主攻目标；用概率方法及矩阵理论构造若干特殊图以确定相应的色数；探讨若干染色的算法复杂性问题。本项目所研究的问题一部分是国际著名学者提出的一些问题， 一部分问题是我们首次提出的，内容涉及到图论、组合优化、算法复杂性等领域。

本项目主要研究图的染色理论、图的谱半径及拓扑指数等问题。用权转移方法研究一类平面图的结构性质，从而探讨这些图类的非正常（列表）染色问题、injective（列表）染色问题、BB-列表染色问题、L(p,q)-标号与对局染色问题。对于非正常（列表）染色，我们针对平面图的3-（可选）可染问题，考虑稍弱的非正常（列表）染色，证明了不含4-圈和6-圈的平面图是（1,1,0）-可染的；不含4,i,j-圈(部分i,j; 4<i<j<k≤9)的平面图是（1,0,0）-可染的。对于图的BB-(列表）-染色，我们主要证明了不含7-圈或8-圈或9-圈且不含相邻4-圈的连通平面图G，存在生成树T，使G关于T的BB色数不超过4,构造了围长为g的连通图G和G的生成树T，使G关于T的BB-色数等于G的色数的2倍减1。给出图的BB-列表染色概念，研究了BB-可选性与k-可选性间的关系。对于injective（列表）染色问题，围绕Wenger猜想展开研究，探讨(g,Δ，c)的值，使得满足围长为g最大度为Δ的平面图G的injective列表色数不超过Δ+c；获得了若干injective列表色数和最大度、最大平均度的关系。对于平面图的L(p,q)-标号问题，给出了不含3,4,7-圈和不含3,4,8-圈的平面图在最大度限制条件下的L(1,1)-标号的上界；同时给出了若干平面图和若干简单图在限制条件下的L(1,1)-标号的上界。对于图的对局染色问题, 我们研究了最大度至少为5的森林和最大度至少为14的外平面图的对局色数的上界。对于图的谱半径问题，我们给出了有向图谱半径的新下界，进而得到有向图能量的新上界；给出了非负不可约矩阵谱半径的新上下界，进而得到图的谱半径的含有参数的新上下界。对于拓扑指数问题，我们研究了Zagreb指数和第三几何算数指数。.本项目所得结果改进了前人的一些工作，推进了一些著名猜想。至今发表了学术论文27篇，其中SCI收录检索的有16篇，应邀参与撰写了《Handbook of Combinatorial Optimization》(Second Edition,Springer, New York (2013))中的“On Coloring Problems” (共96页，与王维凡一起完成)。获浙江省科学技术二等奖1项(排名第三)，培养硕士研究生16名，圆满完成了本课题所预定的研究任务。