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

About 3 years old · traced to

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.

References

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.