Linear Arboricity Conjecture

The Linear Arboricity Conjecture

Definitions and mathematical statement

Shared notation.

Unless a section says otherwise, ${\mathbb{N}}=\{1,2,\ldots\}$, ${\mathbb{Z}}$ is the ring of integers, ${\mathbb{Q}},{\mathbb{R}},{\mathbb{C}}$ are the rational, real, and complex fields, $[N]=\{1,\ldots,\lfloor N\rfloor\}$, and $\log$ is the natural logarithm. For real functions of a parameter tending to infinity, $f\ll g$ and $f=O(g)$ mean $|f|\leq Cg$ eventually for some fixed $C$; $f\gg g$ reverses this comparison; $f=o(g)$ means $f/g\to0$; $f\sim g$ means $f/g\to1$; and $f\asymp g$ means both order bounds. A subscript on $O$ or $\ll$ specifies allowed constant dependence. The expression $n^{o(1)}$ in an upper bound means growth smaller than $n^\epsilon$ for each fixed $\epsilon>0$. Local definitions govern any exception, finite-field convention, or use of the same symbol for another object. An asymptotic claim is not automatically an effective algorithm.

A linear forest is a disjoint union of paths, including isolated vertices. The linear arboricity $\operatorname{la}(G)$ is the least number of linear forests whose edge sets partition $E(G)$. The proposed inequality is $\operatorname{la}(G)\leq\lceil(\Delta(G)+1)/2\rceil$ for every finite simple graph; a vertex may occur in several forest layers. [S1] [S2]

Statement recorded in the supplied source.

Can every graph with maximum degree

\ensuremath{Δ}

be decomposed into at most

\ensuremath{⌈}

$\ensuremath{Δ}+1$/2

\ensuremath{⌉}

linear forests? [S1]

Residual task reported by the archive.

The embedded review $2026-08-17$ records: Prove the stated sharp decomposition bound for every graph. [S1]

Short English statement

Can the edges of every graph be partitioned into the conjectured number of collections of disjoint paths?

Research attempt

Sharp target and literature context.

The required bound includes the $+1$ before division by two. That rounding is essential for even-degree regular graphs, as the counting argument below shows. The primary 2025 manuscript [E1] proves an additive logarithmic-error bound, according to its abstract; such an error term does not establish the exact number of layers required here. The route in this attempt is to separate the maximum-degree constraint from the obstruction caused by monochromatic cycles.

Two unavoidable lower bounds.

If the edges are partitioned into $r$ linear forests, each vertex has degree at most two in each layer. Thus $\Delta\le2r$, giving \[ \operatorname{la}(G)\ge\lceil\Delta/2\rceil. \] A forest on $n$ vertices has at most $n-1$ edges, including isolated vertices when necessary. Therefore for $n\ge2$ and $m=|E(G)|$, \[ \operatorname{la}(G)\ge\left\lceil\frac m{n-1}\right\rceil. \] For a positive even degree $d$ and a $d$-regular graph, $m=dn/2$. The second bound exceeds $d/2$, hence forces at least $d/2+1$ layers. Equivalently, using only $d/2$ layers would require every vertex to have degree two in every layer, so each nonempty layer would be a union of cycles, not a linear forest. This explains the exact proposed ceiling and rules out a tempting one-layer improvement.

A complete solution for forests.

Every forest with maximum degree $\Delta\ge1$ has a proper edge coloring using $\Delta$ colors. One proof deletes a leaf and colors the smaller forest inductively. When restoring its edge, the other endpoint has at most $\Delta-1$ already colored incident edges, so at least one of the $\Delta$ colors is available. Restore isolated vertices freely. This proves the coloring assertion without a general edge-coloring theorem.

Pair these colors, leaving a singleton if necessary. Within each pair a vertex has degree at most two because each color class is a matching. Moreover that subgraph is acyclic because it is a subgraph of the original forest. Its components are therefore paths. This gives $\lceil\Delta/2\rceil$ linear forests, matching the degree lower bound: \[ \operatorname{la}(F)=\lceil\Delta(F)/2\rceil \quad\hbox{for a nonempty forest }F. \] An edgeless graph has linear arboricity zero under the convention that an empty edge partition is allowed.

All graphs of maximum degree two.

A finite connected simple graph of maximum degree two is a path, a cycle, or an isolated vertex. If no cycle component occurs, the whole graph is already a linear forest. If a cycle occurs, at least two layers are necessary. Remove one edge from each cycle and put the removed edges in a second layer. They lie in different components, so that second layer is a matching; the remaining graph is a linear forest. Thus every graph of maximum degree two has linear arboricity at most two, and exactly two if it contains a cycle. This proves the proposed bound throughout this degree range.

Why pairing edge colors does not solve the general case.

Suppose a graph has a proper edge coloring with $q$ colors. Pairing colors always decomposes its edges into $\lceil q/2\rceil$ subgraphs of maximum degree two, but their components may include cycles. Every cycle in one such subgraph alternates its two colors and has even length. The forest proof succeeded because the ambient graph excluded all cycles; that reason disappears here.

For example a four-cycle properly colored alternately with colors one and two produces a cycle when those colors are paired. Removing one edge repairs it, but that edge must be placed somewhere. A receiving layer may already give either endpoint degree two, or adding the edge may close another cycle. Hence a proof requires simultaneous control of endpoint capacity and acyclicity, not just a count of total edges. Even if one invokes the standard $\Delta+1$ edge-coloring bound for simple graphs, pairing colors reaches the desired number of degree-two layers without proving that those layers are linear forests. This attempt does not assume that the missing cycle-elimination step is free.

A concrete tight decomposition beyond forests.

For $K_4$ on vertices $0,1,2,3$, the two paths \[ 0,1,2,3\qquad\hbox{and}\qquad2,0,3,1 \] partition the six edges: their edge sets are respectively $\{01,12,23\}$ and $\{02,03,13\}$. Thus $\operatorname{la}(K_4)=2$, since one layer cannot have degree three. This certificate demonstrates that the cycle issue can be repaired in a small dense example. It does not provide a uniform recoloring rule for arbitrary graphs.

An elementary fallback bound is obtained by greedily coloring edges with $2\Delta-1$ colors: an edge meets at most $2\Delta-2$ already colored edges, so a color remains. Each matching is itself a linear forest. Therefore the parameter is finite with an explicit decomposition, but this bound is far from the sharp target. The fallback cannot be silently substituted for the conjectured ceiling.

Validation, missing lemma, and outcome.

The subclass proofs and the six-edge certificate above are symbolic, with all edges displayed; no large decomposition search is claimed. A possible route would start with paired edge colors and find a potential-decreasing recoloring that removes an alternating cycle without violating endpoint degrees or creating an equally bad cycle elsewhere. This attempt proves no such move exists in every state. The exact remaining gap is that global repair lemma within the same number of layers. The sharp lower bounds, forest formula, and complete degree-two cases do not establish it. Outcome: UNRESOLVED.

Sources

• S1 ULAM.AI, UnsolvedMath, supplied problems.json, record 1419 (GRAPH-032), statement and background. The embedded literature-review date is 2026-08-17; that is the archive’s review date, not a fresh certification. Dataset landing page: https://huggingface.co/datasets/ulamai/UnsolvedMath.

• S2 Linear arboricity overview, Wolfram MathWorld. https://mathworld.wolfram.com/LinearArboricity.html. Bibliographic information from the supplied record.

• E1 Micha Christoph, Nemanja Draganić, António Girão, Eoin Hurley, Lukas Michel, and Alp Müyesser, New bounds for linear arboricity and related problems, arXiv:2507.20500v1. https://arxiv.org/abs/2507.20500. Primary abstract inspected 1 October 2026; it gives $\Delta/2+O(\log n)$ layers, not the exact ceiling for every graph.