Planar graph NP-hardness conjecture for higher divisorial gonality
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.