Cygan et al.'s planar linear arboricity conjecture
Cygan et al.'s planar linear arboricity conjecture
Let be a planar graph with maximum degree . The linear arboricity is the minimum number of linear forests whose union is the edge set of .
Planar Linear Arboricity Conjecture. For every planar graph of maximum degree ,
The conjecture extends the known result for planar graphs of maximum degree at least and would imply the Vizing Planar Graph Conjecture for maximum degree at least , which remains open only when .
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.