# A Proof of Albertson's Conjecture

Preprint · Ankan Sadhu

- Archive id: arxiv:2609.01682
- Published: 2026-09-01
- arXiv: https://arxiv.org/abs/2609.01682
- Source URL: https://arxiv.org/abs/2609.01682
- PDF: https://arxiv.org/pdf/2609.01682
- Provenance: arxiv

## Abstract

Albertson's conjecture states that every graph of chromatic number r has crossing number at least that of the complete graph K\_r. We prove the conjecture for all r. The proof combines new clique-sensitive edge bounds for critical graphs, maximum-clique sampling, and a reserved immersion construction. For graphs of order close to r, we construct edge-disjoint routes while preserving a complete bipartite subgraph whose forced crossings compensate for those introduced when the immersion is smoothed into a drawing. For larger orders, we derive explicit edge bounds using independent-triple deletion and structural properties of critical graphs, then combine them with sampling inequalities that account for crossings within a maximum clique. The remaining numerical inequalities are certified using exact rational arithmetic, with a reproducible certificate and standalone Python verifier.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.