Barát–Thomassen conjecture on tree edge-decompositions

From papers

Let TT be a tree, and let GG be a simple graph. A TT-edge-decomposition is a decomposition of the edges of GG into isomorphic copies of TT. The size of GG is E(G)|E(G)|, and GG is kk-edge-connected if every nonempty proper vertex set AA satisfies dG(A)kd_G(A)\ge k, where dG(A)d_G(A) is the number of edges with exactly one end in AA.

Barát–Thomassen conjecture. For every tree TT, there exists a positive integer kTk_T such that every kTk_T-edge-connected simple graph whose size is divisible by E(T)|E(T)| admits a TT-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

No solutions have been posted yet.