The updated Directed Linear Arboricity Conjecture

Let $D$ be a directed graph, let $\Delta^-(D)$ and $\Delta^+(D)$ denote its maximum indegree and maximum outdegree, and let $\vec{la}(D)$ be the minimum number of colors needed to partition its arcs into directed linear forests. Let $K_n^*$ be the complete symmetric directed graph obtained by replacing every edge of $K_n$ by a pair of antiparallel arcs.

Directed Linear Arboricity Conjecture. For every directed graph $D$ ,

\vec{la}(D)\le\max\{\Delta^-(D),\Delta^+(D)\}+1,

except for $D=K_3^*$ or $K_5^*$ , in which cases

\vec{la}(D)=\max\{\Delta^-(D),\Delta^+(D)\}+2.

The original conjecture was disproved by the two exceptional graphs, according to the source; this updated version is attributed to He, Li, Bai and Sun and is presented as unresolved.

The conjecture, attributed to He, Li, Bai, and Sun, proposes that the two complete symmetric digraphs $K_3^*$ and $K_5^*$ are the only exceptions to the expected bound. It revises the original conjecture of Nakayama and Péroche, which those two graphs disproved.

Known results

He, Li, Bai, and Sun (2017) found $\vec{la}(K_3^*)=4$ with maximum degree $2$ , and $\vec{la}(K_5^*)=6$ with maximum degree $4$ .
The 2023 source records the revised statement as Conjecture 11 and gives no proof or additional exception.

December 2025 list-arboricity result

A paper by the authors of the December 2025 arXiv work proves only an asymptotic list version, $\operatorname{lla}(D)\leq \Delta+6\sqrt{\Delta\log^4\Delta}$ for sufficiently large $\Delta$ . This does not establish the conjectured bound $\Delta+1$ for ordinary directed linear arboricity.

Current status (as of September 2026): The revised conjecture remains unproved; $K_3^*$ and $K_5^*$ are the only known exceptions, and no further counterexample or complete proof is reported.

The updated Directed Linear Arboricity Conjecture

Primary source

Progress summary

Solutions 0