The clique-cutset conjecture for minimally non-perfectly divisible graphs

Let GG) be a graph. 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). A graph is minimally non-perfectly divisible (MNPD) if it is not perfectly divisible but every proper induced subgraph is perfectly divisible. A clique cutset is a clique whose deletion disconnects GG.

Clique-cutset conjecture. No MNPD graph contains a clique cutset.

This conjecture is proposed as an analogue of the folklore result that no minimal imperfect graph contains a clique cutset. Its status is 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

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.