





















Tree-decompositions of graphs are of fundamental importance in structural and algorithmic graph theory. The main property of tree-decompositions is the width (the maximum size of a bag minus 1). We show that every graph has a tree-decomposition with near-optimal width, where each vertex appears in few bags. In particular, every graph with treewidth $k$ has a tree-decomposition with width at most $14k+13$, where each vertex $v$ appears in at most $\text{deg}(v)+1$ bags. This improves an exponential bound by Ding and Oporowski [1995] to linear, and establishes a conjecture of theirs in a strong sense. In a second result, we show that every graph with treewidth $k$ has a tree-decomposition with width at most $3k-1$, where on average each vertex appears in at most three bags.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。