Every graph contains k vertex-disjoint cycles of distinct lengths or has a set of O(k^6 polylog(k)) vertices whose removal leaves at most k-1 cycle lengths.
Large-Treewidth Graph Decompositions and Applications
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
Treewidth is a graph parameter that plays a fundamental role in several structural and algorithmic results. We study the problem of decomposing a given graph $G$ into node-disjoint subgraphs, where each subgraph has sufficiently large treewidth. We prove two theorems on the tradeoff between the number of the desired subgraphs $h$, and the desired lower bound $r$ on the treewidth of each subgraph. The theorems assert that, given a graph $G$ with treewidth $k$, a decomposition with parameters $h,r$ is feasible whenever $hr^2 \le k/\polylog(k)$, or $h^3r \le k/\polylog(k)$ holds. We then show a framework for using these theorems to bypass the well-known Grid-Minor Theorem of Robertson and Seymour in some applications. In particular, this leads to substantially improved parameters in some Erdos-Posa-type results, and faster algorithms for a class of fixed-parameter tractable problems.
fields
math.CO 1years
2026 1verdicts
ACCEPT 1representative citing papers
citing papers explorer
-
An Erd\H{o}s-P\'osa theorem for cycles and faces of distinct lengths
Every graph contains k vertex-disjoint cycles of distinct lengths or has a set of O(k^6 polylog(k)) vertices whose removal leaves at most k-1 cycle lengths.