Polynomial-time 3-colorability of -free graphs with one induced odd cycle length
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.
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
Sign in to submit a solution.
No solutions have been posted yet.