论文标题
归化图的线性树木
Linear arboricity of degenerate graphs
论文作者
论文摘要
线性森林是顶点 - 偶口路径的结合，图$ g $的线性树木均由$ \ operatatorName {la}（g）$表示，是将$ g $的边缘套件划分的最低线性森林数量。显然，$ \ operatorname {la}（g）\ ge \lceilδ（g）/2 \ rceil $ for Graph $ g $，最高度$δ（g）$。另一方面，由于Akiyama，Exoo和Harary引起的线性树木猜想，自1981年以来断言$ \ operatatorName {la}（g）（g）\ leq \ lceil（δ（g）+1 +1） / 2 \ rceil $ for每图$ g $。该猜想已被验证用于平面图和图形最高学位最多$ 6 $，或等于$ 8 $或$ 10 $的平面图和图形。 考虑到一个正整数$ k $，如果可以通过连续删除最多$ k $的顶点，则图表$ g $是$ k $ degenate，如果可以将其简化为琐碎的图。我们证明，对于任何$ k $ -DECENATER GRAPH $ g $，$ \ operatatorName {la}（g）= \lceilΔ（g）/2 \ rceil $提供$δ（g）\ ge 2k^2 -k $。
A linear forest is a union of vertex-disjoint paths, and the linear arboricity of a graph $G$, denoted by $\operatorname{la}(G)$, is the minimum number of linear forests needed to partition the edge set of $G$. Clearly, $\operatorname{la}(G) \ge \lceilΔ(G)/2\rceil$ for a graph $G$ with maximum degree $Δ(G)$. On the other hand, the Linear Arboricity Conjecture due to Akiyama, Exoo, and Harary from 1981 asserts that $\operatorname{la}(G) \leq \lceil(Δ(G)+1) / 2\rceil$ for every graph $ G $. This conjecture has been verified for planar graphs and graphs whose maximum degree is at most $ 6 $, or is equal to $ 8 $ or $ 10 $. Given a positive integer $k$, a graph $G$ is $k$-degenerate if it can be reduced to a trivial graph by successive removal of vertices with degree at most $k$. We prove that for any $k$-degenerate graph $G$, $\operatorname{la}(G) = \lceilΔ(G)/2 \rceil$ provided $Δ(G) \ge 2k^2 -k$.
