Perfect divisibility conjecture for odd hole-free graphs

About 1 year old · traced to

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.

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

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.