The Overfull Nine Dragon Tree Conjecture is True
Mies, Sebastian1; Moore, Benjamin R.2
1 Johannes Gutenberg University Institute of Computer Science Mainz, Germany
2 Institute of Science and Technology Combinatorics and Probablity Group Klosterneuburg Austria
Innovations in Graph Theory, Volume 1 (2024), pp. 21-32.

Chen, Kim, Kostochka, West, and Zhu conjectured a strengthening of the Nine Dragon Tree Theorem that every graph that is (k,d)-sparse and has no overfull set decomposes into k+1 forests such that one of the forests has maximum degree d. Intuitively, the conjecture says that while the fractional arboricity bound in the Nine Dragon Tree Theorem is tight, we can relax the bound very slightly and still get the same result, so long as the obvious obstruction does not occur - that we can still decompose into k+1 forests. We prove this conjecture.

Received:
Accepted:
Published online:
DOI: 10.5802/igt.2
Classification: 05C70
Keywords: Nine Dragon Tree, Fractional arboricity, $(k,d)$-sparse

Mies, Sebastian 1; Moore, Benjamin R. 2

1 Johannes Gutenberg University Institute of Computer Science Mainz, Germany
2 Institute of Science and Technology Combinatorics and Probablity Group Klosterneuburg Austria
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@article{IGT_2024__1__21_0,
     author = {Mies, Sebastian and Moore, Benjamin R.},
     title = {The {Overfull} {Nine} {Dragon} {Tree} {Conjecture} is {True}},
     journal = {Innovations in Graph Theory},
     pages = {21--32},
     publisher = {Stichting Innovations in Graph Theory},
     volume = {1},
     year = {2024},
     doi = {10.5802/igt.2},
     language = {en},
     url = {https://igt.centre-mersenne.org/articles/10.5802/igt.2/}
}
TY  - JOUR
AU  - Mies, Sebastian
AU  - Moore, Benjamin R.
TI  - The Overfull Nine Dragon Tree Conjecture is True
JO  - Innovations in Graph Theory
PY  - 2024
SP  - 21
EP  - 32
VL  - 1
PB  - Stichting Innovations in Graph Theory
UR  - https://igt.centre-mersenne.org/articles/10.5802/igt.2/
DO  - 10.5802/igt.2
LA  - en
ID  - IGT_2024__1__21_0
ER  - 
%0 Journal Article
%A Mies, Sebastian
%A Moore, Benjamin R.
%T The Overfull Nine Dragon Tree Conjecture is True
%J Innovations in Graph Theory
%D 2024
%P 21-32
%V 1
%I Stichting Innovations in Graph Theory
%U https://igt.centre-mersenne.org/articles/10.5802/igt.2/
%R 10.5802/igt.2
%G en
%F IGT_2024__1__21_0
Mies, Sebastian; Moore, Benjamin R. The Overfull Nine Dragon Tree Conjecture is True. Innovations in Graph Theory, Volume 1 (2024), pp. 21-32. doi : 10.5802/igt.2. https://igt.centre-mersenne.org/articles/10.5802/igt.2/

[1] Chen, Min; Kim, Seog-Jin; Kostochka, Alexandr V.; West, Douglas B.; Zhu, Xuding Decomposition of sparse graphs into forests: The Nine Dragon Tree Conjecture for k≤2, Journal of Combinatorial Theory, Series B, Volume 122 (2017), pp. 741 -756 | DOI | MR | Zbl

[2] Cranston, Daniel W. Graph coloring methods, 2024 https://graphcoloringmethods.com (ISBN: 979-8-218-46242-0.) | MR

[3] Grout, Logan; Moore, Benjamin The pseudoforest analogue for the Strong Nine Dragon Tree Conjecture is true, Journal of Combinatorial Theory, Series B, Volume 145 (2020), pp. 433-449 | DOI | MR | Zbl

[4] Jiang, Hongbi; Yang, Daqing Decomposing a Graph into Forests: The Nine Dragon Tree Conjecture is True, Combinatorica, Volume 37 (2017), pp. 1125-1137 | DOI | MR | Zbl

[5] Kim, Seog-Jin; Kostochka, Alexandr V.; West, Douglas B.; Wu, Hehui; Zhu, Xuding Decomposition of Sparse Graphs into Forests and a Graph with Bounded Degree, Journal of Graph Theory, Volume 74 (2013) no. 4, pp. 369-391 | DOI | MR | Zbl

[6] Mies, Sebastian; Moore, Benjamin The Strong Nine Dragon Tree Conjecture is True for d≤2(k+1) (2024) | arXiv

[7] Mies, Sebastian; Moore, Benjamin; Smith-Roberge, Evelyne Beyond the Pseudoforest Strong Nine Dragon Tree Theorem (2023) | arXiv

[8] Mies, Sebastian; Moore, Benjamin R. The Strong Nine Dragon Tree Conjecture is true for d≤k+1, Combinatorica, Volume 43 (2022), pp. 1215-1239 | DOI | MR | Zbl

[9] Montassier, Mickael; Ossona de Mendez, Patrice; Raspaud, André; Zhu, Xuding Decomposing a graph into forests, Journal of Combinatorial Theory, Series B, Volume 102 (2012) no. 1, pp. 38-52 | DOI | MR | Zbl

[10] Nash-Williams, Crispin St. J. A. Decomposition of Finite Graphs Into Forests, Journal of the London Mathematical Society, Volume 39 (1964), p. 12 | DOI | MR | Zbl

[11] Yang, Daqing Decomposing a graph into forests and a matching, Journal of Combinatorial Theory, Series B, Volume 131 (2018), pp. 40 -54 | DOI | MR | Zbl

[12] Zhu, Xuding Refined activation strategy for the marking game, Journal of Combinatorial Theory, Series B, Volume 98 (2008) no. 1, pp. 1-18 | DOI | MR | Zbl

Cited by Sources: