The perfect divisibility and chromatic number of some odd hole-free graphs
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2603.09549
curl -X POST /api/v1/records/arxiv/2603.09549/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2603.09549/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'