NP-completeness of deciding path-chromatic number at most two
NP-completeness of deciding path-chromatic number at most two
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.
Sources & referencesView supporting material
Primary source
Tony Huynh, Bruce Reed, David R. Wood and Liana Yepremyan, “Notes on Tree- and Path-chromatic Number”, arXiv:2002.05363 (2020).
Progress summary
Never refreshed
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.