Barát–Thomassen conjecture on tree edge-decompositions
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.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary 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).
Additional 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.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.