Bonamy et al.'s odd-degree planar edge-partition conjecture

Let GG be a planar graph of odd maximum degree Δ7\Delta\ge 7. A linear forest is a forest whose connected components are paths, and a matching is a set of pairwise vertex-disjoint edges.

Odd-degree planar edge-partition conjecture. The edges of GG can be partitioned into Δ12\tfrac{\Delta-1}{2} linear forests and one matching.

The conjecture seeks a stronger decomposition than the general linear-arboricity bound in the odd-degree planar case. The paper proves this conclusion for odd maximum degree at least 99, leaving the cases covered by the stated conjecture below that threshold open.

Sources & referencesView supporting material

Primary source

Marthe Bonamy, Jadwiga Czyżewska, Łukasz Kowalik and Michał Pilipczuk, “Partitioning edges of a planar graph into linear forests and a matching”, arXiv:2302.13312 (2023).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.