Perfect divisibility conjecture for odd hole-free graphs

From papers

Let GG be a graph with no induced odd cycle of length at least five. A graph is perfectly divisible if, for every induced subgraph HH with at least one edge, its vertex set can be partitioned into AA and BB such that H[A]H[A] is perfect and ω(H[B])<ω(H)\omega(H[B])<\omega(H). 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

No solutions have been posted yet.