图的团横贯和团独立集

The clique-transversals and clique-independent sets of graphs have important application in the design of networks. In mathematical programming, the relaxation forms of clique-transversal problem and clique-independent set problem are mutually dual problems. Specifically, if the girth of the graph G is greater than 3, the clique-transversal and clique-independent set are respectively equivalent to the cover and match of G. We call a graph G clique-perfect if, for every induced subgraph H of G, the clique-transversal number equals the clique-independent number of H. Researching the clique-perfect graphs is a hot topic since, given the clique matrix of the clique-perfect graph, there is a polynomial time algorithm for the two problems. There are mainly two reasons for the importance of clique-transversal problem and clique-independent set problem. On the one hand, cliques are basic, simple and important subgraphs, the researching of clique-transversal problem and clique-independent set problem involves in the analysis of construction of graphs by cliques that will reveal the property and structure of graphs further. On the other hand, the clique-transversal and clique-independent set of graphs are closely related to dominating set, independent set , coloring and so on. In this project, we will use the algorithm design theory and various methods in combinatorics to research the clique-transversal problem and clique-independent set problem in circular-arc graphs, claw-free graphs and planar graphs in which we focus on the characterizing of clique-perfect graphs in the three classes of graphs.

图的团横贯和团独立集在网络设计中有着重要的应用。在数学规划上图的团横贯问题和团独立集问题对应的松弛问题互为对偶问题。特别的，若图的围长大于3，则图的团横贯和团独立集分别等同于图的覆盖和匹配。若对图的任一个导出子图都有团横贯数等于团独立数则称该图是团完美的。研究团完美图是研究团横贯和团独立集的一个热点因为给定图的团矩阵在团完美图上存在团横贯问题和团独立集问题的多项式时间算法。图的团横贯和团独立集受到重视主要有两个方面的原因：一方面，团是图的一个基本而简单的重要子图，图的团横贯和团独立集的研究都涉及到通过图的团来分析图的结构，是从新的角度来认识图，对深入揭示图的结构性质意义重大；另一方面，图的团横贯和团独立集与控制集、独立集、染色等理论的研究密切相关。本课题将利用算法设计理论和各种组合方法在圆弧图、无爪图和平面图这三类重要图类中研究团横贯问题和团独立集问题并重点考虑在这三类图中刻画团完美的图。

图的团横贯问题和团独立集问题在网络设计中有着重要的应用。在数学规划上图的团横贯问题和团独立集问题对应的松弛问题互为对偶问题。特别的，若图的围长大于3，则图的团横贯和团独立集分别等同于图的覆盖和匹配。若对图的任一个导出子图都有团横贯数等于团独立数则称该图是团完美的。研究团完美的图是研究团横贯问题和团独立集问题的一个热点，因为给定团完美图的团矩阵，存在团横贯问题和团独立集问题的线性规划算法。图的团染色问题与图的团横贯问题有着紧密的联系，因为研究图的团染色数可以得到图的团横贯数的一些好的界。. 本项目主要对无爪图以及平面图上的团横贯问题、团独立集问题以及图的团完美性进行研究，并且对圆弧图以及无爪图上的团染色问题做了研究，具体的得到如下研究结果：.(1)我们刻画了无爪平面图上的团完美性，从禁用导出子图的角度给出了无爪平面图是团完美图的一个充分必要条件，该方面的结果已投稿到《Discrete Mathematics》 杂志。.(2)我们在最大度不超过4的无爪图上给出了团横贯问题的多项式时间算法，该方面的成果已在《Information Processing Letters》上发表。.(3)Cerioli 和 Korenchendler 在2009年提出圆弧图上的团染色问题是否线性时间可解的，我们给出了圆弧图上团染色问题的一个线性时间算法，从而解决了他们提出的问题，该方面的成果已在《Journal of Combinatorial Optimization》 上在线发表。.(4)我们证明了最大度不超过7的无爪图是2-团可染色的并且指出最大度为7是必要的，该方面的成果已在《Graph and Combinatorics》 上在线发表。.(5)我们在平面图中定义了分离4-团的定义，给出了不含分离4-团的平面图的团横贯数以及独立数的一些界，该方面的结果已在《应用数学与计算数学学报》上发表。