Polynomial edge-connectivity conjecture for tree edge-decompositions

Let TT be an arbitrary given tree, and let GG be a simple graph. The size of GG is E(G)|E(G)|, and a TT-edge-decomposition is a decomposition of the edges of GG into isomorphic copies of TT.

Polynomial edge-connectivity conjecture. There are two positive integers aa and nn such that every aE(T)na|E(T)|^n-edge-connected simple graph whose size is divisible by E(T)|E(T)| admits a TT-edge-decomposition.

This is proposed as a weaker version of the Barát–Gerbner–Thomassé conjecture, motivated by the paper's quantitative theorem. The source does not state a resolution, so the conjecture remains open.

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).

Progress summary

Never refreshed

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.