← All problems

The Linear Arboricity Conjecture

17 years old · traced to

Let GG be a simple graph, let la(G)=a2(G)la(G)=a_2(G) be its linear arboricity, and let Δ(G)\Delta(G) be its maximum degree. A linear forest is a forest whose connected components are paths.

Linear Arboricity Conjecture. For every simple graph GG,

la(G)≤⌈Δ(G)+12⌉.la(G)\le\left\lceil\frac{\Delta(G)+1}{2}\right\rceil.

The lower bound la(G)≥⌈Δ(G)/2⌉la(G)\ge\lceil\Delta(G)/2\rceil makes this an additive-one assertion. The source reports proofs for several graph classes and asymptotic results, but the conjecture is not stated as resolved in general.

References

3 papers in this index state this conjecture (2009–2023). The statement above is taken from the most recent of them; the others are arXiv:2108.11816, arXiv:0912.5528.

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

Progress summary

Refreshed
Open · progress reported

The conjecture remains open, but recent work extends its framework to infinite graphs and proves additional restricted cases.

Akiyama, Exoo, and Harary proposed the conjecture in 19801980: every simple graph should satisfy la(G)≤⌈(Δ(G)+1)/2⌉la(G)\le\left\lceil(\Delta(G)+1)/2\right\rceil. The general assertion is still unresolved.

Known results

  • Maximum degree at most 33, and maximum degrees 4,5,6,8,104,5,6,8,10, are settled; complete bipartite, series-parallel, planar, and several other classes are known.

October 2026 infinite-graph extension

Aurichi, Monteiro, and Rodrigues report an equivalence between the infinite-graph and finite versions, alongside bounds for topological linear arboricity and regular high-girth graphs. This is a claimed advance, not a proof of the finite conjecture.

Current status (as of October 2026): The conjecture is open for general finite simple graphs; many graph classes and asymptotic regimes are settled, and the infinite-version equivalence is reported but unverified.

Sources

Solutions 0

No solutions have been posted yet.