Polynomial 3-coloring for path-component-free graphs
Converse to Theorem 1.1 (3-Coloring dichotomy for $H$-free graphs) · arXiv:2311.05713
Status open high confidence
The conjecture that 3-Coloring is polynomial-time solvable on $H$-free graphs whenever every component of $H$ is a path is explicitly called 'wide open' in the source paper. The complexity of 3-Coloring on $H$-free graphs has been settled for all $H$ on at most seven vertices, with the two remaining open cases being $H = P_8$ and $H = 2P_4$; no follow-up paper resolving the full conjecture was found in the literature through May 2026.
Reviewer notes. The source paper (arXiv:2311.05713) proves a full dichotomy for List-k-Coloring with k>4 but explicitly leaves the k=3 case open. The main bottleneck cases identified in the literature are P8-free graphs and 2P4-free graphs. A 2025 paper (arXiv:2509.02423) studies 4-coloring of (Pt,C3)-free graphs (NP-hardness direction) but does not touch the 3-coloring/path conjecture. The STACS 2026 paper on list coloring ordered graphs addresses k=4 in a different setting and does not resolve this conjecture.
Context
Theorem 1.1 (Holyer; Kamiński and Lozin) establishes that if $H$ has at least one component which is not a path then the $3$-Coloring Problem on $H$-free graphs is NP-hard. Immediately after stating this theorem the paper notes: 'The converse to Theorem 1.1 is wide open.'
Notes. Not a labelled environment; the open problem is identified by the remark 'The converse to Theorem 1.1 is wide open.' The statement of the converse is implicit and reconstructed from Theorem 1.1.
Source paper
List-$k$-Coloring $H$-free graphs for all $k>4$
Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl · 2023-11-09
https://arxiv.org/abs/2311.05713
PDF source