{"id":"arxiv/2608.14519","url":"https://arxiv.org/abs/2608.14519","tags":["math.CO"],"score":0,"title":"Perfect Divisibility, Linear Divisibility and Chair-Free Graphs","domain":"math.CO","source":"arxiv","authors":["Zhiyu Wang","Weihao Xia"],"reviews":0,"subject":"math.CO","summary":"A graph is perfectly divisible if every induced subgraph with at least one edge admits a partition into a perfect induced subgraph and an induced subgraph with smaller clique number. Every perfectly divisible graph $G$ satisfies $χ(H)\\leq\\binom{ω(H)+1}{2}$ for every induced subgraph $H$ of $G$. We show that the converse fails: for every non-negative integer $t$, the graph $P(17)\\vee K_t$ satisfies this bound for every induced subgraph but is not perfectly divisible, yielding an infinite family of counterexamples. Motivated by this distinction, we introduce $(k,\\ell)$-linear divisibility and…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-14","reactions":{}}