The updated Directed Linear Arboricity Conjecture

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

Directed Linear Arboricity Conjecture. For every directed graph DD,

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

except for D=K3D=K_3^* or K5K_5^*, in which cases

la(D)=max{Δ(D),Δ+(D)}+2.\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.

Sources & referencesView supporting material

Primary source

Ronen Wdowinski, “On an f-coloring generalization of linear arboricity of multigraphs”, arXiv:2301.09933 (2023).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.