Sparse graph decomposition conjecture with no overfull set

Let GG be a graph and let k,dNk,d\in\mathbb{N}. A vertex subset AV(G)A\subseteq V(G) is overfull if

E(G[A])>(k+1)(A1).|E(G[A])|>(k+1)(|A|-1).

A graph is (k,d)(k,d)-sparse when it satisfies the corresponding (k,d)(k,d)-sparseness inequality, and it is (k,d)(k,d)-decomposable if its edges can be decomposed into kk forests and one dd-bounded forest. Sparse graph decomposition conjecture. If GG is (k,d)(k,d)-sparse and has no overfull set, then GG is (k,d)(k,d)-decomposable. This conjecture strengthens the Nine Dragon Tree Conjecture because the fractional-arboricity hypothesis implies both (k,d)(k,d)-sparseness and the absence of overfull sets. The supplied text does not state that this stronger conjecture has been resolved.

Sources & referencesView supporting material

Primary source

Min Chen, Seog-Jin Kim, Alexandr Kostochka, Douglas B. West and Xuding Zhu, “Decomposition of Sparse Graphs into Forests: The Nine Dragon Tree Conjecture for k 2”, arXiv:1502.04755 (2015).

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.