图的圆环染色和分数染色

本项目将研究图的圆环染色和分数染色。图的圆环染色和分数染色均是图的经典染色的自然推广。其研究受到广泛的关注。本项目关注的几个主要问题是线图的圆环色数的取值范围、直积图的圆环色数和分数色数与因子图的圆环色数和分数色数间的关系和3-正则图的分数色数问题。希望找出一些被线图的圆环色数的取值范围覆盖的有理数的区间和一些与线图的圆环色数的取值范围不相交的有理数的区间。得到比较好的大围长的3-正则图的分数色数上界。

本项目着重研究图的染色及相关问题，包括图的圆环染色，带符号图的圆环流、图的反魔方标号，图的分数染色，图的列表染色和在线列表染色以及图的点边赋权等。在图的圆环染色方面，证明了对任意整数n， 区间[n, n+1/6]的任意有理数都是某个有限图的线图的圆环色数，从而否定了Ghebleh有关该问题的一个猜想。本项目比较系统地研究了带符号图的圆环流。将Lovasz-Thomassen-Wu-Zhang关于图的圆环流的突破性结果推广到带符号图的圆环流。关于图的列表染色，Alon-Tarsi证明二部图若最大平均度数为2（k-1），则该图k-可选。我们证明存在二部图，其围长任意大，任意真子图最大平均度数为2（k-1），但不是k-可选的。同时，给出了经典的Erdos定理（存在围长和色数任意大的图）的一个新的、简单的证明。在线列表染色方面， 证明了在线形式的Ohba猜想对独立数不超过3的图成立，证明了局部平面图5-在线可选，强化了著名的Thomasen有关局部平面图5-可染的定理。关于图的点边赋权问题，刻画了所有(2m, m)-在线可选图，否定了Voigt关于3-可选临界图均为(4, 2)-可选的猜想，同时证明一个弱一些的命题成立。对于图的点边赋权问题做了比较多的研究，一个重要的结果是证明了所有图都是点边赋权(2, 3)-可选的。在图的反魔方标号得研究方面，证明了所有度数>1 的正则图均有反魔方标号。为著名的反魔方标号猜想提供了有力的支持。在分数染色方面，在证明了分数形式的Hedetniemi猜想的基础上，研究了图的无重复分数问题，确定了圈图和无二度点的树图的无重复分数色数。本项目共发表了27篇SCI论文。项目组成员获得4项国家自然科学基金面上项目。十多次应邀在重要国际学术会议做大会报告(Plenary Speaker)和邀请报告(Invited Speaker)。