JianLiang Wu

A linear forest is a graph in which each component is a path. A map $\varphi$ from $E(G)$ to $\{1,2,\cdots,t\}$ is called a $t$-linear coloring if the induced subgraph of edges having the same color is a linear forest for $1 \leq \alpha \leq t$. The linear arboricity $la(G)$ of a graph $G$ is the minimum number $t$ for which $G$ has a $t$-linear coloring. Akiyama, Exoo and Harary conjectured that $la(G) =\lceil (\Delta(G)+1)/2 \rceil$ for any regular graph $G$. It is obvious that $la(G)\geq \lceil \Delta (G)/2\rceil $ for any graph $G$ and $la(G)\geq\lceil (\Delta(G)+1)/2\rceil $ for every regular graph $G$. So the conjecture is equivalent to the following conjecture.
Conjecture A. For any graph $G$, $\lceil \frac{\Delta (G)}2\rceil \leq la(G)\leq \lceil \frac{\Delta (G)+1}2\rceil.$
The linear arboricity has been determined for complete bipartite graphs, Halin graphs, series-parallel graphs, complete regular multipartite graphs, and regular graphs with $\Delta=1,2,3,4,5,6,8,10$. P${\rm\acute{e}}$roche proved that the determination of $la(G)$ of a graph $G$ is a \textit{NP}-hard problem, even when $\Delta=4$. Alon, Teague and Wormald proved that there is an absolute constant $c>0$ such that for every $d$-regular graph $G$, $la(G)\leq \frac{d}{2}+cd^{ 2/3}(\log d)^{1/3}$.
Recently, we proved the following results. (1) [2002] An upper bound for the linear arboricity of composition of two graphs and it is proved that for a regular graph $G$ and a null graph $S_n$, $la(G[S_n])=\lceil (\Delta (G[S_n])+1)/2\rceil$ if $\Delta (G)$ is even and $G$ has a Hamiltonian factorization orthogonal to a linear forest, or $\Delta (G)$ is odd and the graph by removing a $1$-factor $F$ from $G$ has a Hamiltonian factorization orthogonal to a matching $M$ such that $M\cup F$ is a linear forest. (2) [2005] If $G$ is a connected graph and $|E|\leq |V|+\lceil{3\Delta/2}-4$, then $la(G)=\lceil{\Delta/2}$. (3) [1999,2006] Conjecture A is true for all planar graphs, Moreover, if $G$ is a planar graph and $\Delta\geq 11$, then $la(G)=\lceil{\Delta/2}$. Other related results are obtained, too. (4) [2005] If a graph $G$ can be embedded in a surface of Euler characteristic $\varepsilon< 0$ and $\Delta(G)\geq \sqrt{46-54\varepsilon}+19$, then its linear arboricity is $ \lceil{\Delta(G)}\rceil$.