Open Research Index

Perfect divisibility and perfect-Pollyanna in bull-free graphs

Ran Chen, Paras Vinubhai Maniya, Di Wu, Junran Yu

arXivarxiv/2603.21538Mar 23, 2026math.COscore 0

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:…

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2603.21538
curl -X POST /api/v1/records/arxiv/2603.21538/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2603.21538/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'