Perfect divisibility conjecture for odd hole-free graphs
Let be a graph with no induced odd cycle of length at least five. A graph is perfectly divisible if, for every induced subgraph with at least one edge, its vertex set can be partitioned into and such that is perfect and . Perfect divisibility conjecture. Every odd hole-free graph is perfectly divisible. This would extend several known perfect-divisibility results for odd hole-free graphs under additional forbidden-subgraph conditions, including the absence of a claw, cochair, dart, bull, odd balloon, fork, or banner. The general case remains unresolved in the supplied source.
References
Primary source
Weihua He, Yueping Shi, Rong Wu and Zheng-an Yao, “The perfect divisibility and chromatic number of some odd hole-free graphs”, arXiv:2603.09549 (2026).
Additional references
3 papers in this index state this conjecture (2025–2026). The statement above is taken from the most recent of them; the others are arXiv:2603.01967, arXiv:2503.10206.
Progress summary
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.