Tree T-decomposition via maximum degree connectivity

Conjecture 1.2 · arXiv:1507.08208

arXiv Conjecture high confidence— first stated 2016-06-30

Authors: Julien Bensmail, Ararat Harutyunyan, Tien-Nam Le, Stéphan Thomassé

Status disproved high confidence

Conjecture 1.2 from arXiv:1507.08208, which posits a function $f$ such that $f(\Delta_T)$-edge-connectivity and minimum degree $f(|E(T)|)$ suffice for $T$-decomposition for any tree $T$, is disproved by Klimošová and Thomassé (arXiv:1803.03704): for trees of maximum degree 3 (specifically complete binary trees of arbitrary depth), no such function $f$ exists. The path case ($\Delta_T \leq 2$, already proved in the source paper) was subsequently strengthened by arXiv:1907.11600, establishing that 3-edge-connectivity is optimal for paths.

Cited literature (2)

counterexample Edge-decomposing graphs into coprime forests (2018)

Tereza Klimošová, Stéphan Thomassé · Journal of Graph Theory · arXiv:1803.03704

Constructs a counterexample to Conjecture 1.2 for trees of maximum degree 3 using complete binary trees $T_k$ of arbitrary depth $k$, showing that no function $f$ can make the conjecture hold for such trees.
partial Edge-partitioning 3-edge-connected graphs into paths (2019)

Tereza Klimošová, Stéphan Thomassé · Journal of Combinatorial Theory, Series B · arXiv:1907.11600

Proves the path case of Conjecture 1.2 with optimal 3-edge-connectivity (replacing the 24-edge-connectivity of the source paper), establishing $f(2)=3$ is achievable, and notes the general conjecture fails for trees of maximum degree 3.

Reviewer notes. Conjecture 1.2 is disproved in full generality by arXiv:1803.03704 for trees of maximum degree ≥ 3. The path subcase (ΔT ≤ 2) remains valid and was settled optimally at 3-edge-connectivity by arXiv:1907.11600. The related Barát-Thomassen Conjecture 1.1 (connectivity depending on |E(T)| without minimum degree condition) was proved separately and is a distinct result.

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

Conjecture. There is a function $f$ such that, for any fixed tree $T$ with maximum degree $\Delta_T$, every $f(\Delta_T)$-edge-connected graph with its number of edges divisible by $|E(T)|$ and minimum degree at least $f(|E(T)|)$ can be $T$-decomposed.

Context

The authors propose this as a refinement of the Barát-Thomassen Conjecture (Conjecture 1.1), arguing that the large edge-connectivity required in Conjecture 1.1 can be replaced by a constant depending only on the maximum degree of $T$, provided the host graph has sufficiently large minimum degree. The present paper proves Conjecture 1.2 in the case $\Delta_T \leq 2$, i.e., when $T$ is a path.

Notes. PDF source — math symbols rendered as unicode in extraction; LaTeX reconstructed from context.

Source paper

Edge-partitioning a graph into paths: beyond the Barát-Thomassen conjecture
Julien Bensmail, Ararat Harutyunyan, Tien-Nam Le, Stéphan Thomassé · 2016-06-30
https://arxiv.org/abs/1507.08208 PDF source