The List Linear Arboricity of Digraphs

A (directed) linear forest is a graph whose components are (directed) paths. The linear arboricity la(F) of a (di)graph F is the minimum number of (directed) linear forests required to decompose its edges. Akiyama, Exoo, and Harary (1980) conjectured that la(G)≤⌈((Δ+1))⁄2⌉ for any graph G of maximum degree Δ. The current best bound is due to Lang and Postle (2023), who showed la(G)≤ Δ/2+ 3√Δ log^4 Δ for sufficiently large Δ. And they proved this in the stronger list setting proposed by An and Wu (1999). For digraphs, let its maximum degree be the maximum of out-degrees and in-degrees of its vertices. Nakayama and Peroche (1987) conjectured that la(D)≤Δ+1 for any digraph D with maximum degree Δ. We extend Lang and Postle’s result to digraphs with matching error term. We show that any digraph D with maximum degree Δ admits a decomposition into at most Δ + 6√Δ log^4 Δ directed linear forests when Δ is sufficiently large. And we also show this in the list setting. Joint work with Yueping Shi.