Sparse graph decomposition conjecture with no overfull set

About 11 years old · traced to

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

∣E(G[A])∣>(k+1)(∣A∣−1).|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.

References

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.