The P5-free perfect divisibility conjecture
The P5-free perfect divisibility conjecture
Let denote the chordless path on five vertices. 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 .
P5-free conjecture. Every -free graph is perfectly divisible.
The conjecture is proposed in connection with the paper's clique-cutset results. Chudnovsky and Sivaraman proved the related result that -free graphs are perfectly divisible; the stated conjecture remains open.
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
Chính T. Hoàng, “On the structure of perfectly divisible graphs”, arXiv:2506.12660 (2025).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.