Polynomial-time 3-colorability of PtP_t-free graphs with one induced odd cycle length

From papers

For any integer tt and any odd integer kk, let Gt,k\mathcal{G}_{t,k} be the class of graphs that are PtP_t-free and whose induced odd cycles all have length kk. Polynomial-time 3-coloring conjecture. For any fixed tt and kk, the 3-coloring problem for Gt,k\mathcal{G}_{t,k} can be solved in polynomial time.

This claim concerns the complexity of 3-coloring a restricted graph class, motivated by results on graphs with prescribed induced cycle lengths. The source gives no resolution status for this statement.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Yidong Zhou, Mingxian Zhong and Shenwei Huang, “3-Coloring P_t-Free Graphs With Only One Prescribed Induced Odd Cycle Length”, arXiv:2512.06367 (2025).

Solutions 0

No solutions have been posted yet.