2025/12/23 by Yueping Shi, Ping Hu, Shi, Yueping +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Interconnection Networks and Systems #Graph theory and applications
paper · doi:10.48550/arxiv.2512.20195
A (directed) linear forest is a (di)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) proposed the Linear Arboricity Conjecture that la(G) ≤ \lceil (Δ+1)/(2)\rceil for any graph G of maximum degree Δ. The current best known bound, due to Lang and Postle (2023), establishes la(G) ≤ \fracΔ2 + 3√Δ log4 Δ for sufficiently large Δ. And they proved this in the stronger list setting proposed by An and Wu. For a digraph D, let its maximum degree Δ(D) be the maximum of all in-degrees and out-degrees of its vertices. Nakayama and Péroche (1987) conjectured that la(D) ≤ Δ(D)+1 for every digraph D. We extend Lang and Postle's result to digraphs with a matching error term. We show that la(D) ≤Δ+ 6√Δ log4 Δ for any digraph D with Δ= Δ(D) sufficiently large. Moreover, we also establish this bound in the stronger list setting, where each arc e ∈ A(D) is assigned a list of colors, and each arc is assigned a color from its list such that each color class forms a directed linear forest.