NP-hardness of List-k-Coloring on rP₃-free graphs

Status solved high confidence

The open question asks whether List-$k$-Coloring on $rP_3$-free graphs is NP-hard for some $k\in\mathbb{N}$. arXiv:2311.05713 (Chudnovsky, Hajebi, Spirkl; Combinatorica 2024) proves a full complexity dichotomy for all $k>4$: List-$k$-Coloring on $H$-free graphs is polynomial-time solvable whenever every component of $H$ is a path on at most three vertices, and $rP_3$ satisfies this condition. Combined with the source paper's polynomial result for $k=5$ and classical results for $k\leq 4$, List-$k$-Coloring on $rP_3$-free graphs is polynomial-time solvable for all $k\in\mathbb{N}$, answering the open question in the negative.

Cited literature (2)

• proof List-k-Coloring H-free graphs for all k>4 (2023)
  Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl · Combinatorica 44 (2024) · arXiv:2311.05713 · doi:10.1007/s00493-024-00106-2

  Proves that for all k>4, List-k-Coloring on H-free graphs is polynomial-time solvable when every component of H is a path on at most 3 vertices (covering all rP3), thereby establishing that no k exists for which List-k-Coloring on rP3-free graphs is NP-hard.

• partial Maximum List r-Colorable Induced Subgraphs in kP3-Free Graphs (2025)
  Esther Galby, Paloma T. Lima, Andrea Munaro, Amir Nikabadi · arXiv preprint · arXiv:2505.00412

  Generalizes polynomial-time solvability to Max-Weight List r-Colorable Induced Subgraph on kP3-free graphs for all fixed r and k, providing a short self-contained proof of List r-Coloring polynomial-time solvability as a special case.

Reviewer notes. The open question is definitively answered in the negative: List-k-Coloring on rP3-free graphs is polynomial-time solvable for all k in N. The key paper arXiv:2311.05713 was already present in the supplied internal references (2311.05713__01). The 2025 paper arXiv:2505.00412 further generalizes the result to the weighted setting.

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