Restricting Odd Antiholes in Critical Graphs via List Coloring
By the Strong Perfect Graph Theorem, every graph whose chromatic number exceeds its clique number contains an odd hole or an odd antihole. We investigate the structure of odd antiholes in critical graphs with fixed maximum degree. We prove that if $G$ is a $k$-critical graph with maximum degree $Δ$ then every odd antihole in $G$ has length at most $2(Δ-k)+7$, and conjecture that, in the odd-hole-free setting, equality forces the graph itself to be the corresponding odd antihole. We verify this extremal characterization when $Δ\geq 2k-5$, extending recent results for $Δ=k$, and construct…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.14241
curl -X POST /api/v1/records/arxiv/2610.14241/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.14241/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'