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 solved high confidence

A 2019 theorem of Cames van Batenburg, Huynh, Joret, and Raymond gives an O_H(k log(k+1)) vertex Erdős–Pósa bound for every fixed planar H, and taking H to be a grid proves the conjecture.

Cited literature (1)

proof A tight Erdős–Pósa function for planar minors (2018)

See linked article · Existing literature or final source version

A 2019 theorem of Cames van Batenburg, Huynh, Joret, and Raymond gives an O_H(k log(k+1)) vertex Erdős–Pósa bound for every fixed planar H, and taking H to be a grid proves the conjecture.

Read the literature-status audit

Reviewer notes. These status corrections report results attributed to existing papers or to the final source version. Graph-Theory-LLM-Proofs located and checked the implication; it is not credited as the author of the result. Audit caveat: The deduction is complete but relies on the published planar-minor Erdős–Pósa theorem rather than reproving it; the catalog appears to have missed arXiv:1807.04969.

Auto-reviewed 2026-09-01 with gpt-5.6-sol.

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