树分解及其应用

A tree decomposition of a graph maps each vertex of the graph to a subtree of some tree, such that the intersection of two subtrees, mapped correspondingly from any two adjacent vertices of the graph, are nonempty. It can be used to measure the tree-likeness of a graph. Also tree decompositions have been widely studied for their applications in algorithmic design..In this project, we will study two classes of tree decompositions with some structure properties and the applications of tree decompositions in some coloring problems, mainly including the following three parts: (1) the time complexity of computing a minimum size tree decomposition of width at most 3; and the algorithms for finding a minimum size tree decomposition of width at most k in the class of graphs of treewidth at most t≥k; (2) the structural properties of the class of graphs having 2-super-caterpillar tree decompositions; and the complexity of deciding whether a given graph with bounded treewidth has a 2-super-caterpillar tree decomposition; (3) tree chromatic number, which is a new parameter combining the tree decompositions and chromatic number together; vertex arboricity is a special parameter related with coloring problem; We will study the structural properties of graphs with bounded tree chromatic number and the vertex arboricity of graphs with bounded treewidth. The research will give more insight into the difficulty of designing practical algorithms for computing tree-decompositions; and it will improve the applications of the tree decompositions in practice.

一个图的树分解将图中的每个顶点都映射到一棵树的某个子树上,并且满足每两个相邻的顶点所映射到的子树是相交的。树分解可以用于研究一个图的树相似度,在算法设计中起着非常重要的作用。.本项目旨在研究两类特殊的树分解及其在一些染色问题中的应用,拟进行三方面的研究:(1) 宽度至多是3的最小树树分解的计算复杂度；以及在树宽至多是k的图类中，求解宽度至多是t≥k的最小树树分解的算法; (2) 存在2-超毛毛虫树分解的图类的结构特征; 以及判定树宽有界的图类是否存在2-超毛毛虫树分解的计算复杂度；(3)树色数问题是将树分解与染色问题结合起来的新一类染色问题;点荫度是一种特殊的顶点染色数，本项目拟研究有界树色数图类的结构特征,以及树宽有界的图类的点荫度。本项目的研究可以丰富树分解的相关理论知识, 更深入理解宽度有界的树分解的计算难点，促进树分解在解决实际问题中的应用。

本项目主要研究了树分解及其在染色问题中的应用，具体包括k-超毛毛虫树分解和最小树树分解的计算复杂性问题，树色数问题，树染色问题以及1-2-3猜想相关问题。我们证明了树宽至多是4的不包含三角形的图其树色数至多是2；设计了树染色问题以树宽为参数的FPT算法；并且证明了均匀树染色问题在区间图类里是以树宽为参数的W[1]-hard问题，但同时证明了在树宽有界的图类里，该问题是多项式可解的，并对弦图设计了该问题的2-近似算法，还给出了该问题的第一个不可近似性结果；最后，关于1-2-3猜想的两个相关问题：给定一个树宽有界的图和整数k，我们设计了多项式时间算法，计算出用{1, 2, 3, …, k}中的值给图中所有边赋值时，顶点所得的颜色数，即其所关联的所有边的赋值之和，的最大值的最小值， 同时要求所得的顶点染色要求是正常染色；另外，当1-2-3猜想中要求所得顶点染色是单射染色时，对于树宽至多是1的图类，即森林，我们证明了边的赋值最大是该图的最大度数。本项目的研究将树分解深入地应用到了多种染色问题中，丰富了应用树分解解决实际问题的理论基础。