Math Conjectures

Linear Arboricity Conjecture

OPENMajorConjectureProposed 1980–1981 · Standard version

Canonical statement

Let la⁡(G)\operatorname{la}(G) be the least number of linear forests (forests whose components are paths, including isolated edges) whose edge sets partition E(G)E(G). Every finite simple graph GG with maximum degree Δ(G)\Delta(G) satisfies
la⁡(G)≤⌈Δ(G)+12⌉. \operatorname{la}(G)\leq \left\lceil\frac{\Delta(G)+1}{2}\right\rceil.
View source LaTeX
Let \(\operatorname{la}(G)\) be the least number of linear
forests (forests whose components are paths, including isolated edges)
whose edge sets partition \(E(G)\). Every finite simple graph \(G\) with
maximum degree \(\Delta(G)\) satisfies
\[
  \operatorname{la}(G)\leq
  \left\lceil\frac{\Delta(G)+1}{2}\right\rceil.
\]
GRAPH-018:[AkiyamaExooHarary1981][Alon1988Linear][ChristophEtAl2025Linear]
Graph theoryCombinatorics

Notes

A linear forest is a graph each of whose components is a path, and the linear arboricity la⁡(G)\operatorname{la}(G) is the least number of linear forests whose edge sets partition E(G)E(G). A vertex of degree Δ(G)\Delta(G) meets each linear forest in at most two edges, so la⁡(G)≥⌈Δ(G)/2⌉\operatorname{la}(G)\ge\lceil\Delta(G)/2\rceil, and for regular graphs one further forest is forced. The conjecture, proposed by Akiyama, Exoo, and Harary around 1980–1981, asserts that la⁡(G)≤⌈(Δ(G)+1)/2⌉\operatorname{la}(G)\le\lceil(\Delta(G)+1)/2\rceil always suffices [AkiyamaExooHarary1981].

Alon proved the conjecture asymptotically, showing la⁡(G)=Δ/2+o(Δ)\operatorname{la}(G)=\Delta/2+o(\Delta) as Δ→∞\Delta\to\infty and introducing probabilistic arguments that have shaped subsequent work [Alon1988Linear]. The lower-order error term has since been sharpened repeatedly, recently by Christoph, Draganić, Girão, Hurley, Michel, and Müyesser [ChristophEtAl2025Linear], and the exact bound is known for many degree ranges and for numerous graph classes.

The conjecture is thus true up to lower-order terms, but the exact ceiling for every maximum degree remains unproved, and closing the gap between Δ/2+o(Δ)\Delta/2+o(\Delta) and the conjectured value is the outstanding task.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.