论文标题
$ d \ leq k+1 $的九龙树猜想是正确的
The Strong Nine Dragon Tree Conjecture is true for $d \leq k+1$
论文作者
论文摘要
无向图$ g =（v，e）$的树木$γ（g）$是最小的数字，因此可以将$ e $划分为$γ（g）$ sorests。 Nash -Williams的公式指出，$ k = \lceilγ（g）\ rceil $，其中$γ（g）$是$ {| e_h |}/（| e_h |}/（| v_h | -1）$（| v_h | -1）$（v_h，e_h，e_h，e_h）$ g $ g $ g $ g $ | v_h | \ geq 2 $。 强烈的九龙树的猜想指出，如果$γ（g）\ leq k+\ frac {d} {d+k+1} $ for $ k，in \ in \ mathbb n_0 $，那么$ g $的边缘集合$ g $ in $ k+1 $ fore to $ k+1 $ forests of $ k+forests of $ k+forest to yos $ d $ d $ d $ d $ d $ edges in connectioncect in connect connectionconty comments in connectiond comments in connect comments。 我们以$ d \ leq k + 1 $的价格解决了猜想。对于$ d \ leq 2（k+1）$，我们无法证明猜想，但是我们证明存在一个分区，其中一个森林中的连接组件最多具有$ d+\ lceil k \ cdot \ cdot \ frac \ frac {d} {k+1} {k+1} \ rceil -k $ evges。 作为该定理的应用，我们表明每$ 5 $ - 连接的平面图$ g $都具有$ \ frac {5} {6} {6} $ - 薄跨度树。从某种意义上说，即使我们更换$ 4 $ - 边缘连接的$ 5 $ - 边缘连接，也是最好的，即使我们替换了$ \ frac {5} {6} $，任何正面实际数量小于$ 1 $，也是如此。这加强了默克和邮政的结果，默克和邮政显示$ 6 $ - 边缘连接的平面图具有$ \ frac {18} {19} {19} $ - 薄跨度树。
The arboricity $Γ(G)$ of an undirected graph $G = (V,E)$ is the minimal number such that $E$ can be partitioned into $Γ(G)$ forests. Nash-Williams' formula states that $k = \lceil γ(G) \rceil$, where $γ(G)$ is the maximum of ${|E_H|}/(|V_H| -1)$ over all subgraphs $(V_H, E_H)$ of $G$ with $|V_H| \geq 2$. The Strong Nine Dragon Tree Conjecture states that if $γ(G) \leq k + \frac{d}{d+k+1}$ for $k, d \in \mathbb N_0$, then there is a partition of the edge set of $G$ into $k+1$ forests such that one forest has at most $d$ edges in each connected component. We settle the conjecture for $d \leq k + 1$. For $d \leq 2(k+1)$, we cannot prove the conjecture, however we show that there exists a partition in which the connected components in one forest have at most $d + \lceil k \cdot \frac{d}{k+1} \rceil - k$ edges. As an application of this theorem, we show that every $5$-edge-connected planar graph $G$ has a $\frac{5}{6}$-thin spanning tree. This theorem is best possible, in the sense that we cannot replace $5$-edge-connected with $4$-edge-connected, even if we replace $\frac{5}{6}$ with any positive real number less than $1$. This strengthens a result of Merker and Postle which showed $6$-edge-connected planar graphs have a $\frac{18}{19}$-thin spanning tree.
