NP-completeness of deciding path-chromatic number at most two

For a graph GG, let path-χ(G)\mathsf{path}\textnormal{-}\chi(G) denote its path-chromatic number. Path-chromatic two-colourability conjecture. It is NP-complete to decide if path-χ(G)2\mathsf{path}\textnormal{-}\chi(G) \leqslant 2. 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

No solutions have been posted yet.