Graphs and Matroids Seminar - Ronen Wdowinski

Title: Linear arboricity of sparse multigraphs via orientations

Abstract:

The linear arboricity $la(G)$ of a loopless multigraph $G$ is the minimum number of colors required to edge-color $G$ into linear forests, that is, forests whose components are all paths. The Linear Arboricity Conjecture of Akiyama, Exoo, and Harary asserts that the linear arboricity of a simple graph $G$ is at most $\lceil (\Delta(G)+1)/2 \rceil$. We prove the conjecture when $\Delta(G) \ge 4pa(G) - 2$, where $pa(G)$ is the pseudoarboricity of $G$. This improves previously known results on the linear arboricity of sparse graphs, and our result holds more generally for loopless multigraphs. Our proof is a simple application of a characterization of multigraphs with indegree- and outdegree-restricted orientations.