Two short proofs concerning tree-decompositions.

*(English)*Zbl 1018.05081The 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.

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.

Reviewer: Oriol Serra (Barcelona)

##### MSC:

05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |