An Approximate Version of the Strong Nine Dragon Tree Conjecture
| Autor: | Mies, Sebastian, Moore, Benjamin |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | We prove the Strong Nine Dragon Tree Conjecture is true if we replace the edge bound with $d + \big\lceil k \big\lfloor\frac{d-1}{k+1}\big\rfloor \big(\frac{d}{k+1} - \frac{1}{2} \big\lceil\frac{d}{k+1}\big\rceil \big)\big\rceil \leq d + \frac{k}{2} \cdot \big(\frac{d}{k+1}\big)^2$. More precisely: let $G$ be a graph, let $d$ and $k$ be positive integers and $\gamma(G) = \max_{H \subseteq G, v(H) \geq 2} \frac{e(H)}{v(H) - 1}$. If $\gamma(G) \leq k + \frac{d}{d + k + 1}$, then there is a partition of $E(G)$ into $k + 1$ forests, where in one forest every connected component has at most $d + \big\lceil k \big\lfloor\frac{d-1}{k+1}\big\rfloor \big(\frac{d}{k+1} - \frac{1}{2} \big\lceil\frac{d}{k+1}\big\rceil \big)\big\rceil$ edges. Comment: 20 pages, 4 figures. arXiv admin note: text overlap with arXiv:2403.05178 |
| Databáze: | arXiv |
| Externí odkaz: |
|