Paperlane

no. 14 · Friday 13 November 2026

Some properties of minimally nonperfectly divisible graphs

Qiming Hu, Baogang Xu and Miaoxia Zhuang

math.CO · v3

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
pdf ↗ page arXiv:2603.01967 ↗