NP-hardness conjecture for promise graph coloring
Statement
For integers , is the promise problem of coloring a graph with colors under the promise that it is -colorable. Promise-coloring hardness conjecture. For every , the promise problem is NP-hard. The source states that this basic problem remains wide open.
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.