On Scott's odd induced subgraph conjecture and a related problem
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2604.19727
curl -X POST /api/v1/records/arxiv/2604.19727/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.19727/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'