zbMATH — the first resource for mathematics

Two short proofs concerning tree-decompositions. (English) Zbl 1018.05081
The authors give a short and nice proof of the key theorem of R. Thomas [J. Comb. Theory, Ser. B 48, 67-76 (1990; Zbl 0636.05022)] which states that any finite graph \(G\) admits a tree-decomposition of width the treewidth of \(G\) which is linked. A tree-decomposition of \(G\) is linked if, for every \(k\geq 0\) and any two of its pieces \(P\) and \(Q\), either there are \(k\) disjoint paths between \(P\) and \(Q\) or there is a third piece \(R\) between \(P\) and \(Q\) with at most \(k-1\) vertices.
The proof relies on a basic lemma which also provides a short derivation of the tree-width duality theorem of Seymour and Thomas saying that the treewidth of a graph equals the maximum \(k\) such that there is a collection of connected subgraphs, pairwise intersecting or adjacent, such that no set of at most \(k\) vertices meets all of them.

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Full Text: DOI