论文标题
低退化图图的线性树木猜想
The linear arboricity conjecture for graphs of low degeneracy
论文作者
论文摘要
线性森林是一个无环图，每个连接的组件都是路径。或者换句话说，它是一个无环图，其最高度最高为2。 $ g $的线性树木为$χ'_l（g）$是$ g $的任何线性着色所需的最小颜色数量。很容易看到，对于任何图$ g $，$χ'_l（g）\ geq \ left \ lceil \ frac {δ（g）} {2} {2} {2} \ right \ rceil $，其中$Δ（g）$是$ g $的最大程度。 1980年的Akiyama，Exoo和Harary的线性树木猜想指出，对于每个图$ G $，$χ'_l（g）\ leq \ leq \ left \ lew \ lceil \ frac {Δ（g）+1} +1} {2} {2} \ right \ right \ rceil $。 Basavaraju等。表明该猜想对于3级图是正确的，并提供了用于计算线性着色的线性时间算法，最多最多使用$ \ left \ lceil \ frac {δ（g）+1} {2} {2} \ right \ rceil $ $ $ $ $ $ $。最近，Chen，Hao和Yu表明$χ'_l（g）= \ left \ lceil \ frac {δ（g）} {2} {2} \ right \ rceil $对于任何$ k $ -degenate graph $ g $，具有$Δ（g）\ geq 2k^2k^2-k $。从此结果，我们有$χ'_l（g）= \ left \ lceil \ frac {δ（g）} {2} {2} \ right \ rceil $，每3级图$ g $ a，$ g $ $ g $ $Δ（g）\ geq q q q geq 15 $。我们表明，这种平等性能每3级图$ g $具有$δ（g）\ geq 9 $。此外，通过扩展所使用的技术，我们在3级图上显示了线性树木猜想的不同证明。接下来，我们证明，对于每一个2级图$ g $，$χ'_l（g）= \ left \ lceil \ frac {δ（g）} {2} {2} \ right \ rceil \ rceil $如果$Δ（g）\ geq 5 $。我们猜想，当$δ（g）\ in \ {3,4 \} $中时，这种平等也存在，并证明了某些众所周知的2级图的子类是这种情况。
A linear forest is an acyclic graph whose each connected component is a path; or in other words, it is an acyclic graph whose maximum degree is at most 2. A linear coloring of a graph $G$ is an edge coloring of $G$ such that the edges in each color class form a linear forest. The linear arboricity of $G$, denoted as $χ'_l(G)$, is the minimum number of colors required in any linear coloring of $G$. It is easy to see that for any graph $G$, $χ'_l(G)\geq\left\lceil\frac{Δ(G)}{2}\right\rceil$, where $Δ(G)$ is the maximum degree of $G$. The Linear Arboricity Conjecture of Akiyama, Exoo and Harary from 1980 states that for every graph $G$, $χ'_l(G)\leq \left \lceil \frac{Δ(G)+1}{2}\right\rceil$. Basavaraju et al. showed that the conjecture is true for 3-degenerate graphs and provided a linear time algorithm for computing a linear coloring using at most $\left\lceil\frac{Δ(G)+1}{2}\right\rceil$ colors for any input 3-degenerate graph $G$. Recently, Chen, Hao and Yu showed that $χ'_l(G)=\left\lceil\frac{Δ(G)}{2}\right\rceil$ for any $k$-degenerate graph $G$ having $Δ(G)\geq 2k^2-k$. From this result, we have $χ'_l(G)=\left\lceil\frac{Δ(G)}{2}\right\rceil$ for every 3-degenerate graph $G$ having $Δ(G)\geq 15$. We show that this equality holds for every 3-degenerate graph $G$ having $Δ(G)\geq 9$. Moreover, by extending the techniques used, we show a different proof for the Linear Arboricity Conjecture on 3-degenerate graphs. Next, we prove that for every 2-degenerate graph $G$, $χ'_l(G)=\left\lceil\frac{Δ(G)}{2}\right\rceil$ if $Δ(G)\geq 5$. We conjecture that this equality holds also when $Δ(G)\in\{3,4\}$ and show that this is the case for some well-known subclasses of 2-degenerate graphs.
