PSPACE-completeness conjecture for the on-line chromatic number
Statement
Let be a graph and let . The on-line chromatic number conjecture. Deciding whether
is \textsc{PSPACE}-complete.
The complexity of deciding whether the on-line chromatic number satisfies this bound was open in the paper; it was known to be \textsc{coNP}-hard and to lie in \textsc{PSPACE}. The paper proves \textsc{PSPACE}-completeness when a pre-coloring is supplied, motivating this conjecture for the unprecolored problem.
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.