The Linear Arboricity Conjecture for 3-Degenerate Graphs

Abstract

A k-linear coloring of a graph G is an edge coloring of G with k colors so that each color class forms a linear forest—a forest whose each connected component is a path. The linear arboricity χl′(G) of G is the minimum integer k such that there exists a k-linear coloring of G. Akiyama, Exoo and Harary conjectured in 1980 that for every graph G, χl′(G)≤⌈Δ(G)+12⌉ where Δ(G) is the maximum degree of G. We prove the conjecture for 3-degenerate graphs. This establishes the conjecture for graphs of treewidth at most 3 and provides an alternative proof for the conjecture for triangle-free planar graphs. Our proof also yields an O(n)-time algorithm that partitions the edge set of any 3-degenerate graph G on n vertices into at most ⌈Δ(G)+12⌉ linear forests. Since χl′(G)≥⌈Δ(G)2⌉ for any graph G, the partition produced by the algorithm differs in size from the optimum by at most an additive factor of 1. © 2020, Springer Nature Switzerland AG.