Barát–Thomassen conjecture on tree edge-decompositions
Let be a tree, and let be a simple graph. A -edge-decomposition is a decomposition of the edges of into isomorphic copies of . The size of is , and is -edge-connected if every nonempty proper vertex set satisfies , where is the number of edges with exactly one end in .
Barát–Thomassen conjecture. For every tree , there exists a positive integer such that every -edge-connected simple graph whose size is divisible by admits a -edge-decomposition.
This is the fundamental edge-decomposition conjecture attributed to Barát and Thomassen (2006). The paper presents stronger quantitative results for graphs with sufficiently large minimum degree, while the general assertion concerns arbitrary simple graphs and remains the motivating conjecture here.
References
8 papers in this index state this conjecture (2012–2022). The statement above is taken from the most recent of them; the others are arXiv:1611.07486, arXiv:1603.00197, arXiv:1603.00198, arXiv:1509.06393, arXiv:1507.08208, arXiv:1505.04309, arXiv:1203.1671.
Status
- Solved: Julien Bensmail, Ararat Harutyunyan, Tien-Nam Le, Martin Merker and Stéphane Thomassé. A Proof of the Barát-Thomassen Conjecture (Journal of Combinatorial Theory, Series B, 2017) https://arxiv.org/abs/1603.00197
Source: Morteza Hasanvand, “Edge-decompositions of O(m)-edge-connected graphs into isomorphic copies of a fixed tree of size m”, arXiv:2205.10871 (2024).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.