错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Tree-Partitions with Bounded Degree Trees

  • Marc Distel,
  • David R. Wood

摘要

A tree-partition of a graph G is a partition of V(G) such that identifying the vertices in each part gives a tree. It is known that every graph with treewidth k and maximum degree \(\Delta \) has a tree-partition with parts of size \(O(k\Delta )\) . We prove the same result with the extra property that the underlying tree has maximum degree \(O(\Delta )\) .