T-decomposition by leaf count of trees

Conjecture 5 · arXiv:1907.11600

arXiv Conjecture high confidence— first stated 2019-07-26

Authors: Tereza Klimošová, Stéphan Thomassé

Status open medium confidence

No verified proof or disproof of Conjecture 5 was found. The conjecture asks for a function f bounding the required edge-connectivity for T-decompositions in terms of the number of leaves of T, with the paper's main result establishing f(2)=3 for paths. A Semantic Scholar citation query identified at least two post-2019 papers citing the source paper — Hasanvand (arXiv:2205.10871, 2022) on O(m)-edge-connected tree decompositions and Hylasová–Kaiser (arXiv:2405.02049, 2024) — but neither could be fully fetched to confirm specific claims about Conjecture 5 within the web-call budget.

Reviewer notes. The Barát–Thomassen conjecture (bounding connectivity by maximum degree of T) was already proved before 2019; Conjecture 5 proposes the sharper bound via number of leaves. Two candidate follow-up papers were surfaced via the Semantic Scholar citations API but could not be verified by WebFetch within the 5-call cap: (1) Hasanvand, 'Edge-decompositions of O(m)-edge-connected graphs into isomorphic copies of a fixed tree of size m' (arXiv:2205.10871, 2022), whose title suggests potential partial progress; (2) Hylasová and Kaiser, 'Hypertree Shrinking Avoiding Low Degree Vertices' (arXiv:2405.02049, 2024). These should be checked in a follow-up review.

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 $m$ leaves, every $f(m)$-edge-connected graph with minimum degree at least $f(|E(T)|)$ and number of edges divisible by $|E(T)|$ has a $T$-decomposition.

Context

This conjecture is posed by the paper's authors as an alternative to Conjecture 2 (which fails for trees of maximum degree three), bounding the required edge-connectivity in terms of the number of leaves of $T$ rather than its maximum degree. The paper's main result implies $f(2) = 3$ is achievable, and the authors note that establishing the existence of $f(3)$ would already contain the claw case.

Source paper

Edge-partitioning 3-edge-connected graphs into paths
Tereza Klimošová, Stéphan Thomassé · 2019-07-26
https://arxiv.org/abs/1907.11600 PDF source