The P5-free perfect divisibility conjecture

From papers

Let P5P_5 denote the chordless path on five vertices. A graph is perfectly divisible if every induced subgraph with at least one edge has a partition (A,B)(A,B) such that the induced graph on AA is perfect and (G[B])<(G)(G[B])<(G).

P5-free conjecture. Every P5P_5-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 (P5,bull)(P_5,\operatorname{bull})-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

No solutions have been posted yet.