k-Coloring dichotomy for H-free graphs

Full dichotomy for $k$-Coloring on $H$-free graphs ($k\geq 3$) · arXiv:2311.05713

arXiv Informal medium confidence— first stated 2023-11-09

Authors: Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl

Status open high confidence

The full dichotomy of $k$-Coloring on $H$-free graphs remains open for every $k\geq 3$. The source paper settled the analogous List-$k$-Coloring dichotomy for $k>4$ but explicitly noted that for plain $k$-Coloring (without lists) no value of $k\geq 3$ is known for which the polynomial/NP-hard boundary is fully characterised. For $k=3$, open cases such as $H=P_8$ and $H=2P_4$ persist; for $k=4$, a 2025 paper narrows the complexity gap for $(P_t,C_3)$-free graphs (showing NP-hardness for $t\in\{19,20,21\}$) but a complete characterisation remains elusive. No follow-up paper resolves the conjecture for any single value of $k$.

Cited literature (1)

partial Coloring Problem in $(P_t,C_3)$-free Graphs (2025)

Unknown (arXiv 2509.02423) · arXiv preprint · arXiv:2509.02423

Proves NP-completeness of 4-Coloring on $(P_t,C_3)$-free graphs for $t\in\{19,20,21\}$, narrowing the complexity gap for 4-Coloring in this two-forbidden-subgraph family but leaving the full $k$-Coloring dichotomy open.

Reviewer notes. The conjecture is distinct from the List-k-Coloring dichotomy, which was settled by the source paper itself for k>4. For plain k-Coloring, the smallest open cases for k=3 are H=P_8 and H=2P_4; for k=4 the complexity of Pt-free graphs for 7<=t<=18 is unknown. No paper found that resolves the dichotomy for any single k>=3.

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

Informal. For every integer $k \geq 3$, characterise the graphs $H$ for which the $k$-Coloring Problem restricted to $H$-free graphs is polynomial-time solvable versus NP-hard.

Context

The paper observes that, in contrast with the List-$k$-Coloring Problem (now settled for all $k>4$), 'for the $k$-Coloring Problem, no value of $k\geq 3$ is known for which the "easy" choices of $H$ are completely distinguished from the "hard" ones.' This identifies a broad open problem motivating the paper's List-$k$-Coloring results.

Notes. Not a labelled environment; the open problem is implicit in the motivating remark in the introduction. Statement reconstructed from context.

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