Odd-Δ planar linear arboricity with matching

Conjecture 2 · arXiv:2302.13312

arXiv Conjecture high confidence— first stated 2023-02-26

Authors: Marthe Bonamy, Jadwiga Czyżewska, Łukasz Kowalik, Michał Pilipczuk

Status partial high confidence

The conjecture holds for all odd Δ ≥ 9: the case Δ ≥ 11 follows from prior linear arboricity results, and the source paper (arXiv:2302.13312) resolves Δ = 9. The sole remaining open case is Δ = 7. A targeted web search and citation lookup (Semantic Scholar) found no post-2023 paper resolving the Δ = 7 case.

Reviewer notes. The Δ = 7 case is the only remaining open instance. One citing paper was found (arXiv:2304.03256, Banerjee et al., 2023, JGT) but it studies the computational complexity of decomposing into a matching and a k-bounded linear forest and makes no claim about the planar Δ = 7 conjecture. No resolution of the full conjecture found after 5 web calls.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Conjecture. For every planar graph $G$ of odd maximum degree $\Delta \geq 7$ the edges of $G$ can be partitioned into $\frac{\Delta-1}{2}$ linear forests and one matching.

Context

This conjecture refines the known linear arboricity bound for planar graphs with odd maximum degree by replacing one linear forest with the weaker structure of a matching. The case $\Delta \geq 11$ follows from existing results; the paper resolves $\Delta = 9$ (Theorem 2), leaving $\Delta = 7$ as the sole remaining open case.

Source paper

Partitioning edges of a planar graph into linear forests and a matching
Marthe Bonamy, Jadwiga Czyżewska, Łukasz Kowalik, Michał Pilipczuk · 2023-02-26
https://arxiv.org/abs/2302.13312 PDF source