图的团染色及其相关算法研究

The clique-coloring can be considered as a variant of vertex-coloring of graphs and also a special partition problem. The clique-coloring of graphs is closely related to the Ramsey number. The clique-coloring of a graph G is an assignment of some colors to the vertices of G such that no maximal clique of G is monochromatic. Obviously, if the graph G has no triangle, the clique-coloring of G is equivalent to the vertex-coloring of G. Since the clique-coloring of G has no hereditary, the research of the clique-coloring will be more complicated than the usual vertex-coloring. In 1991, Duffus asked that whether there is a constant C such that all perfect graphs are C-clique-colorable in J. Combinatorial Theory A. From then, many experts have proved that many classes of perfect graphs are 2-clique-colorable or 3-clique-colorable. Recently, some experts from France have found a sub-class of perfect graphs of arbitrary large clique-coloring number in J. Combin. Theory Ser. B. So the research of clique-coloring becomes more and more interesting. In this project, we will use the algorithm design theory and various methods in combinatorics to research the clique-coloring of graphs and related algorithms in which we focus on the clique-coloring of perfect graphs, planar graphs and claw-free graphs.

图的团染色可看做图的点染色的变体，也可看作一类特殊的划分问题，与图的Ramsey 数有着紧密的联系。图的团染色可定义为给图的点染色使得图中的每一个极大团具有至少两种颜色。显然如果图中不存在三角形，则图的团染色就等同于图的点染色。由于图的团染色不具有遗传性，从而图的团染色与图的点染色相比研究起来将更加复杂。1991年，Duffus等人在组合论杂志A上提出是否存在一个整数C满足所有的完美图是C-团可染色的。围绕该问题，许多图论专家证明了大量的完美图子类是2-团可染色的或3-团可染色的。2016年，法国的图论专家在组合论杂志B上给出了一类团染色数可以任意大的完美图，从而否定了完美图的团染色数是有界的猜想，这使得完美图上的团染色数以及团染色算法研究越来越具有趣味性。本项目将利用算法设计理论和各种组合方法研究图的团染色及其相关算法并重点关注完美图、平面图和无爪图上的团染色问题。

图的团染色可看做图的点染色的变体，也可看作一类特殊的划分问题，与图的Ramsey数有着紧密的联系。图的团染色可定义为给图的点染色使得图中的每一个极大团具有至少两种颜色。显然如果图中不存在三角形，则图的团染色就等同于图的点染色。由于图的团染色不具有遗传性，从而图的团染色与图的点染色相比研究起来将更加复杂。本项目利用算法设计理论和各种组合方法主要在平面图、无爪图等图类上做出了如下主要结果。1. 在一般平面图中给出了一个3-团染色的线性时间算法，从而给出了平面图是3-团可染色的一个新的证明。该方面的成果发表在 Operations Research Letters 杂志。2. 证明了平面图是列表4-团可染色的并且给出了一个列表4-团可染色的线性时间算法。并且证明了不含K5-minor的图仍然是列表4-团可染色的，该结果是对Mohar和Skrekovski 的结果的推广。该方面的结果发表在Discrete Mathematics 杂志。3. 在外平面图上给出了一个最优团染色的线性时间算法并且在外平面图上刻画了图的团完美性。该方面的成果发表在Journal of Combinatorial Optimization 杂志。4. 首先指出了完全图的线图的团染色数与推广的Ramsey数之间的一个联系,其次对于最大度不超过7的线图给出了一个最优团染色的多项式时间算法, 该方面的成果发表在运筹学学报杂志。5. 在不含爪以及K4的平面图中给出了团横贯问题的一个多项式时间算法，该方面的成果发表在Information Processing Letters 杂志。