{"id":"arxiv/2604.19727","url":"https://arxiv.org/abs/2604.19727","tags":["math.CO"],"score":0,"title":"On Scott's odd induced subgraph conjecture and a related problem","domain":"math.CO","source":"arxiv","authors":["Bo Ning"],"reviews":0,"subject":"math.CO","summary":"For a graph $G$, let $f_o(G)$ denote the maximum order of an induced subgraph of $G$ all of whose vertices have odd degree, and let $χ(G)$ denote the chromatic number of $G$. Scott (CPC, 1992) proved that $f_o(G) \\ge |V(G)|/(2χ(G))$ for every graph without isolated vertices, and conjectured that the factor $2$ can be removed. Wang and Wu (JGT, 2024) showed that this conjecture fails for bipartite graphs, but holds for line graphs. In this article, we confirm Scott's conjecture for claw-free graphs without isolated vertices, thereby strengthening the result of Wang and Wu. We also construct…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-04-21","reactions":{}}