Let G be a simple graph, let la(G)=a_2(G) be its linear arboricity, and let Delta(G) be its maximum degree. A linear forest is a forest whose connected components are paths. Linear Arboricity Conjecture. For every simple graph G, la(G)≤lceil fracDelta(G)+12rceil. The lower bound la(G)≥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.

The Linear Arboricity Conjecture

About 17 years old · traced to 2009

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

Linear Arboricity Conjecture. For every simple graph $G$ ,

la(G)\le\left\lceil\frac{\Delta(G)+1}{2}\right\rceil.

The lower bound $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

Primary source

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

Additional 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.

Posted 1 month ago · edited 5 days ago

Progress summary

Refreshed 5 days ago

Claimed progress

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 $1980$ : every simple graph should satisfy $la(G)\le\left\lceil(\Delta(G)+1)/2\right\rceil$ . The general assertion is still unresolved.

Known results

Maximum degree at most $3$ , and maximum degrees $4,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

No solutions have been posted yet.