{"id":"arxiv/2603.09549","url":"https://arxiv.org/abs/2603.09549","tags":["math.CO"],"score":0,"title":"The perfect divisibility and chromatic number of some odd hole-free graphs","domain":"math.CO","source":"arxiv","authors":["Weihua He","Yueping Shi","Rong Wu","Zheng-an Yao"],"reviews":0,"subject":"math.CO","summary":"A hole is an induced cycle of length at least 4, and an odd hole is a hole of odd length. It is NP-hard to color the vertices of an odd hole-free graph. A graph $G$ is perfectly divisible if every induced subgraph $H$ of $G$ with at least one edge admits a partition of $V(H)$ into sets $A$ and $B$ such that $H[A]$ is perfect and $ω(H[B])<ω(H)$. $G$ is short-holed if every hole in $G$ has length 4. A hammer is the graph obtained by identifying one vertex of a $K_3$ and one end vertex of a $P_3$. In this paper, we prove that (i) (odd hole, hammer, $K_{2,3}$)-free graphs are perfectly…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-03-10","reactions":{}}