Perfect divisibility conjecture for odd hole-free graphs
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.
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
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.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.