← All problems

Cygan et al.'s planar linear arboricity conjecture

4 years old · traced to

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.

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.

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.