ProbXiv
Explorersign in
Problem archiveProblem record

Statement

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.

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 in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.