Polynomial 3-coloring for P_t-free graphs

Question 1.1 · arXiv:1806.11196

arXiv Question high confidence— first stated 2018-07-02

Authors: Maria Chudnovsky, Shenwei Huang, Sophie Spirkl, Mingxian Zhong

Status partial high confidence

Substantial partial progress has been made: the 3-coloring (and list 3-coloring) problem is known to be polynomial for all $P_t$-free graphs with $t \leq 7$, with the $P_7$ case resolved by Bonomo, Chudnovsky, Maceli, Schaudt, Stein, and Zhong around 2018. For $t \geq 8$ the question remains fully open; $P_8$-free graphs are the smallest unsettled case. Since 2018, incremental progress has appeared for specific subclasses of $P_t$-free graphs (e.g., those with restrictions on odd cycle lengths), but no uniform polynomial algorithm for all fixed $t$ is known.

Cited literature (1)

partial 3-Coloring $P_t$-Free Graphs With Only One Prescribed Induced Odd Cycle Length (2025)

unverified from abstract page · arXiv preprint · arXiv:2512.06367

Proves a polynomial-time algorithm for 3-coloring $P_{10}$-free graphs whose only induced odd cycles have a single prescribed length (e.g., 7-cycles), a restricted but non-trivial subclass of $P_t$-free graphs.

Reviewer notes. The conjecture is proven for $t \leq 7$; the $P_7$ result (Bonomo et al., ~2018) is the furthest general case. For $t \geq 8$ the problem is open and listed as such in recent surveys (e.g., open problems from the 33rd Workshop on Cycles and Colourings, arXiv:2511.02892, 2025). Additional post-2018 partial progress found in search but not fetched: '3-Colouring $P_t$-Free Graphs Without Short Odd Cycles' (Algorithmica 2022, link.springer.com/article/10.1007/s00453-022-01049-0) and 'Three-coloring triangle-free graphs without long forbidden paths' (arXiv:2512.12349, 2025) — these were not WebFetched and are excluded from since_posted per policy.

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

Question. Is it true that for every (fixed) integer $t > 0$, the 3-coloring problem can be solved in polynomial time when restricted to the class of $P_t$-free graphs?

Context

Theorem 1.1 (from the literature) states that if the $k$-coloring problem is polynomial on $H$-free graphs then every connected component of $H$ must be a path. For $k=3$ the converse may hold — it is known to fail for $k>4$ — so the question of whether $P_t$-free graphs always admit a polynomial-time 3-coloring algorithm remains open. The present paper contributes a positive result for the subclass of $(P_6+rP_3)$-free graphs.

Notes. The question has no explicit attribution citation in the header; it is recorded as a standing open problem in the field by the paper's authors. Full paper text was truncated in the supplied PDF extraction, so later sections could not be checked for additional conjectural statements.

Source paper

List-three-coloring graphs with no induced $P_6+rP_3$
Maria Chudnovsky, Shenwei Huang, Sophie Spirkl, Mingxian Zhong · 2018-07-02
https://arxiv.org/abs/1806.11196 PDF source