The linear arboricity conjecture for graphs of low degeneracy

Abstract

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 ${\chi }_l^{\prime }(G)$, is the minimum number of colors required in any linear coloring of $G$. It is easy to see that for any graph $G$, ${\chi }_l^{\prime }(G)\ge \lceil \frac{\Delta (G)}{2}\rceil$, where $\Delta (G)$ is the maximum degree of $G$. The Linear Arboricity Conjecture of Akiyama, Exoo and Harary from 1980 states that for every graph $G$, ${\chi }_l^{\prime }(G)\le \lceil \frac{\Delta (G)+1}{2}\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 $\lceil \frac{\Delta (G)+1}{2}\rceil$ colors for any input 3-degenerate graph $G$. Recently, Chen, Hao and Yu showed that ${\chi }_l^{\prime }(G)=\lceil \frac{\Delta (G)}{2}\rceil$ for any $k$-degenerate graph $G$ having $\Delta (G)\ge 2k^2-k$. From this result, we have ${\chi }_l^{\prime }(G)=\lceil \frac{\Delta (G)}{2}\rceil$ for every 3-degenerate graph $G$ having $\Delta (G)\ge 15$. We show that this equality holds for every 3-degenerate graph $G$ having $\Delta (G)\ge 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$, ${\chi }_l^{\prime }(G)=\lceil \frac{\Delta (G)}{2}\rceil$ if $\Delta (G)\ge 5$. We conjecture that this equality holds also when $\Delta (G)\in \{3,4\}$ and show that this is the case for some well-known subclasses of 2-degenerate graphs.

20 pages, 4 figures