Planar graph NP-hardness conjecture for higher divisorial gonality
Planar graph NP-hardness conjecture for higher divisorial gonality
For a fixed positive integer , let the Divisorial Gonality problem ask whether a graph has divisorial gonality at most a given integer, and let the Stable Divisorial Gonality problem ask the analogous question after allowing subdivisions. Planar higher-gonality hardness conjecture. The Divisorial Gonality and Stable Divisorial Gonality remain NP-hard when the inputs are restricted to planar graphs. The preceding results establish NP-hardness for bipartite and apex graphs; the planar case is left as a conjecture.
Sources & referencesView supporting material
Primary source
Ralph Morrison and Lucas Tolley, “Computing higher graph gonality is hard”, arXiv:2208.03573 (2022).
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.