{"id":"arxiv:2609.01682","kind":"preprint","title":"A Proof of Albertson's Conjecture","authors":["Ankan Sadhu"],"author_count":1,"year":2026,"published":"2026-09-01","venue":null,"cited_by":null,"doi":null,"arxiv_id":"2609.01682","nct_id":null,"source_url":"https://arxiv.org/abs/2609.01682","archive_url":"https://space-kitty.com/papers/arxiv:2609.01682","updated":"2026-10-12","pmid":null,"pmcid":null,"openalex_id":null,"pdf_url":"https://arxiv.org/pdf/2609.01682","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_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"retracted":false,"peer_reviewed":false,"categories":["math.CO","cs.CG","cs.DM"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.","topics":[],"cited_in_dossiers":[]}