NP-completeness of planar linear arboricity at maximum degree four
NP-completeness of planar linear arboricity at maximum degree four
Let be a planar graph with maximum degree . Its linear arboricity is the minimum number of linear forests whose union is the edge set of .
Planar degree-four linear arboricity complexity conjecture. It is NP-complete to determine whether
The paper identifies this as the only remaining case in its discussion of planar graphs: the cases of odd maximum degree are immediate, maximum degree at least are settled by the main theorem, and the planar linear arboricity conjecture would settle maximum degrees and .
Sources & referencesView supporting material
Primary source
Marek Cygan, Lukasz Kowalik and Borut Luzar, “A Planar Linear Arboricity Conjecture”, arXiv:0912.5528 (2009).
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.