{"id":"arxiv/2603.21538","url":"https://arxiv.org/abs/2603.21538","tags":["math.CO","cs.DM"],"score":0,"title":"Perfect divisibility and perfect-Pollyanna in bull-free graphs","domain":"math.CO","source":"arxiv","authors":["Ran Chen","Paras Vinubhai Maniya","Di Wu","Junran Yu"],"reviews":0,"subject":"math.CO","summary":"A graph $G$ is {\\em perfectly divisible} if, for each induced subgraph $H$ of $G$, $V(H)$ can be partitioned into $A$ and $B$ such that $H[A]$ is perfect and $ω(H[B])<ω(H)$. A {\\em bull} is a graph consisting of a triangle with two disjoint pendant edges. Hoàng [Discrete Math. 349 (2026) 114809] proposed four conjectures: 1. $P_5$-free graphs are perfectly divisible; 2. Odd hole-free graphs are perfectly divisible; 3. Even hole-free graphs are perfectly divisible; and 4. $4K_1$-free graphs are perfectly divisible. Karthick et al. [Electron. J. Combin. 29 (2022) P3.19] proposed a conjecture:…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-03-23","reactions":{}}