Albertson's Conjecture for Chromatic Numbers at Most 29
Albertson's conjecture asserts that every finite simple graph $G$ with $χ(G) \ge r$ satisfies $\operatorname{cr}(G) \ge \operatorname{cr}(K_r)$. Building on Cranston's verification for $r \le 24$ and his reduction of $r \in \{25,26\}$ to three residual orders, we eliminate those residual cases and then prove the cases $r=27,28,29$. The first structural ingredient is a Kempe-chain construction: if a $k$-critical graph has a vertex of degree $k-1$, then it contains a branch-clean essential immersion of $K_k$. Essential immersions are crossing-monotone, so a critical counterexample must have…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.04771
curl -X POST /api/v1/records/arxiv/2609.04771/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.04771/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'