Sparse graph decomposition conjecture with no overfull set
Sparse graph decomposition conjecture with no overfull set
Let be a graph and let . A vertex subset is overfull if
A graph is -sparse when it satisfies the corresponding -sparseness inequality, and it is -decomposable if its edges can be decomposed into forests and one -bounded forest. Sparse graph decomposition conjecture. If is -sparse and has no overfull set, then is -decomposable. This conjecture strengthens the Nine Dragon Tree Conjecture because the fractional-arboricity hypothesis implies both -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.