The updated Directed Linear Arboricity Conjecture
The updated Directed Linear Arboricity Conjecture
Let be a directed graph, let and denote its maximum indegree and maximum outdegree, and let be the minimum number of colors needed to partition its arcs into directed linear forests. Let be the complete symmetric directed graph obtained by replacing every edge of by a pair of antiparallel arcs.
Directed Linear Arboricity Conjecture. For every directed graph ,
except for or , in which cases
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.