Tree-Partitions with Small Bounded Degree Trees

2022/10/23 by Marc Distel, David R. Wood, Distel, Marc +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2210.12577

openalex publication_date 2022/10/23 · openalex created_date 2022/10/31 · openalex updated_date 2026/07/28

Abstract

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 Δ has a tree-partition with parts of size O(kΔ). We prove the same result with the extra property that the underlying tree has maximum degree O(Δ) and O(|V(G)|/k) vertices.

Cited by

• Tree decompositions with small width, spread, order and degree

Related

• Partitions and Coverings of Trees by Bounded-Degree Subtrees
• Partitioning sparse graphs into an independent set and a forest of\n bounded degree
• Bipartite partition-connected factors with small degrees
• Maximum and minimum degree conditions for embedding trees
• Partitioning graphs with linear minimum degree