Polynomial-time 3-colorability of -free graphs with one induced odd cycle length
For any integer and any odd integer , let be the class of graphs that are -free and whose induced odd cycles all have length . Polynomial-time 3-coloring conjecture. For any fixed and , the 3-coloring problem for 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.
References
- 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).
Progress summary
Never refreshed
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.