图的树宽的结构性结果(英文)

Structural Aspects on the Treewidth of Graphs

图G的树宽是使得G成为一个k-树的子图的最小整数k.树宽的算法性结果在图子式理论及有关领域中已有深入的研究.本文着重讨论其结构性结果,包括拓扑不变性、子式单调性、可分解性、刻画问题、与其它参数的关系及由此引伸出的性质.

The treewidth of a graph G is the minimum integer k such that G is a subgraph of a k-tree. The algorithmic aspects of this notion have been well studied in graph minor theory and related areas. This paper is concerned with the structural aspects of treewidth, including the topological invariance, the minor monotonicity, the decomposability, relations with other parameters, and related results.