no. 14 · Friday 13 November 2026
Some properties of minimally nonperfectly divisible graphs
Abstract
A graph is perfectly divisible if every induced subgraph $H$ admits a partition $(A,B)$ of $V(H)$ such that $H[A]$ is perfect and $ω(H[B])<ω(H)$. A graph is minimally nonperfectly divisible if it is not perfectly divisible but every proper induced subgraph is perfectly divisible. We prove that every $P_2\cup P_4$-free or diamond-free minimally nonperfectly divisible graph has no homogeneous set, and that every $2P_3$-free or claw-free minimally nonperfectly divisible graph has no clique cutset. We also study the relationship between perfect divisibility and its weighted analogue, perfect weight divisibility, defined for positive integral vertex weights. We prove that if a graph $H$ has no adjacent twins, then every $H$-free graph is perfectly divisible if and only if every $H$-free graph is perfectly weight divisible.
- fields
- Combinatorics