The even-hole-free perfect divisibility conjecture
The even-hole-free perfect divisibility conjecture
A hole is a chordless cycle with at least four vertices, and an even hole is a hole of even length. A graph is perfectly divisible if every induced subgraph with at least one edge has a partition such that the induced graph on is perfect and .
Even-hole-free conjecture. Every even-hole-free graph is perfectly divisible.
The source notes that every even-hole-free graph contains a bisimplicial vertex, where a bisimplicial vertex has a neighbourhood covered by two cliques. The perfect divisibility conjecture remains open.
Sources & referencesView supporting material
Primary source
Chính T. Hoàng, “On the structure of perfectly divisible graphs”, arXiv:2506.12660 (2025).
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
Sign in to submit a solution.
No solutions have been posted yet.