3-colourability complexity of P_t-free graphs

Status partial high confidence

The open problem asks to determine whether 3-colourability of $P_t$-free graphs (for $t \geq 8$) can be decided in polynomial time or is NP-hard; the question is not settled. The subexponential-time algorithm of the source paper was significantly improved to quasi-polynomial time $n^{\mathcal{O}(\log^2 n)}$ by Pilipczuk, Pilipczuk, and Rz\k{a}\.zewski (2020), using techniques from Independent Set in $P_t$-free graphs. A 2025 paper by Zhou, Zhong, and Huang establishes a polynomial-time algorithm for the restricted class $\mathcal{G}_{10,7}$ ($P_{10}$-free graphs with all induced odd cycles of the same length 7), but the full complexity boundary for $t \geq 8$ remains open.

Cited literature (2)

• partial Quasi-polynomial-time algorithm for Independent Set in $P_t$-free graphs via shrinking the space of induced paths (2020)
  Marcin Pilipczuk, Michał Pilipczuk, Paweł Rzążewski · arXiv preprint · arXiv:2009.13494

  Extends the quasi-polynomial-time Independent Set framework to 3-Coloring of $P_t$-free graphs, achieving runtime $n^{\mathcal{O}(\log^2 n)}$, a major improvement over the subexponential bound of the source paper.

• partial 3-Coloring $P_t$-Free Graphs With Only One Prescribed Induced Odd Cycle Length (2025)
  Yidong Zhou, Mingxian Zhong, Shenwei Huang · arXiv preprint · arXiv:2512.06367

  Gives a polynomial-time algorithm for 3-coloring graphs in $\mathcal{G}_{10,7}$ (the class of $P_{10}$-free graphs whose induced odd cycles all have length exactly 7), extending polynomial tractability to a new subclass.

Reviewer notes. Polynomial-time solvability vs.~NP-hardness for 3-colourability of $P_t$-free graphs with $t \geq 8$ remains open. The strongest known upper bound is quasi-polynomial time $n^{\mathcal{O}(\log^2 n)}$ (Pilipczuk et al., 2020), improving the subexponential bound of Conjecture 1803.05396. Polynomial-time results exist only for restricted subclasses (e.g., $\mathcal{G}_{10,7}$). No NP-hardness result for any fixed $t \geq 8$ is known.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).