NP-completeness of deciding path-chromatic number at most two
Statement
For a graph , let denote its path-chromatic number. Path-chromatic two-colourability conjecture. It is NP-complete to decide if . The source states this alongside the tree-chromatic claim, but does not explicitly introduce it with the phrase “we conjecture”; the surrounding context presents it as part of the same unresolved complexity question.
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.