Planar graph NP-hardness conjecture for higher divisorial gonality

For a fixed positive integer rr, let the rthr^{th} Divisorial Gonality problem ask whether a graph has divisorial gonality at most a given integer, and let the rthr^{th} Stable Divisorial Gonality problem ask the analogous question after allowing subdivisions. Planar higher-gonality hardness conjecture. The rthr^{th} Divisorial Gonality and rthr^{th} 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

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.