Cygan et al.'s planar linear arboricity conjecture

Let GG be a planar graph with maximum degree Δ5\Delta\ge 5. The linear arboricity la(G){\rm la}(G) is the minimum number of linear forests whose union is the edge set of GG.

Planar Linear Arboricity Conjecture. For every planar graph GG of maximum degree Δ5\Delta\ge 5,

la(G)=Δ2.{\rm la}(G)=\left\lceil \tfrac{\Delta}{2} \right\rceil.

The conjecture extends the known result for planar graphs of maximum degree at least 99 and would imply the Vizing Planar Graph Conjecture for maximum degree at least 66, which remains open only when Δ=6\Delta=6.

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).

Additional references

2 papers in this index state this conjecture (2022–2023). The statement above is taken from the most recent of them; the others are arXiv:2207.07169.

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.