Treewidth packing with k log k bound

Conjecture 1.4 · arXiv:1710.06282

arXiv Conjecture high confidence— first stated 2018-07-05

Authors: Pierre Aboulker, Samuel Fiorini, Tony Huynh, Gwenaël Joret, Jean-Florent Raymond, Ignasi Sau

Status open high confidence

Conjecture 1.4 from arXiv:1710.06282 — that every graph of treewidth at least f(r)·k·log(k+1) has k vertex-disjoint subgraphs each of treewidth at least r — remains open as of May 2026. No resolution was found in the indexed literature; the conjecture is a treewidth-level analogue of the more general planar-H Erdős-Pósa conjecture (Conjecture 1.2 of the same paper), and is implied by it via the r×r grid. The Chekuri–Chuzhoy framework (arXiv:1304.1577) achieves a weaker c′≥1 factor but does not attain the tight k log(k+1) bound asserted here.

Reviewer notes. No follow-up paper was found that proves, disproves, or makes substantial partial progress on Conjecture 1.4 specifically. The conjecture is implied by the broader Conjecture 1.2 (Erdős-Pósa for any fixed planar H), which also appears to remain open. The two internal-corpus candidate references (2108.01162 and 2404.05992) are false positives from fuzzy matching and do not address this conjecture.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Conjecture. There is a function $f : \mathbb{N} \to \mathbb{N}$ such that for all integers $r, k \geq 1$, every graph $G$ of treewidth at least $f(r) \cdot k \log(k + 1)$ has $k$ vertex-disjoint subgraphs $G_1, \ldots, G_k$, each of treewidth at least $r$.

Context

This is the treewidth-level analogue of Conjecture 1.2: it asserts that $c' = 1$ suffices in Theorem 1.3 of Chekuri and Chuzhoy (at least ignoring the precise dependence on $r$), whereas their proof only gives $c' \geq 1$. The authors note it is implied by Conjecture 1.2 by taking $H$ to be the $r \times r$ grid.

Notes. Section 4 (open problems) is cut off in the source text; additional items may be present but are not extractable.

Source paper

A tight Erdős-Pósa function for wheel minors
Pierre Aboulker, Samuel Fiorini, Tony Huynh, Gwenaël Joret, Jean-Florent Raymond, Ignasi Sau · 2018-07-05
https://arxiv.org/abs/1710.06282 PDF source