Delphi.science

The Strong Perfect Graph Theorem

Source: github.com/mahdi-jfri/StrongPerfectGraphTheorem/tree/f81220…

Arshia Soltani Moakhar, Iman Gholami, Max Springer, Mahdi JafariRaviz, MohammadTaghi Hajiaghayi

Palomar Registrypalomar/PALOMAR-2026-11-06-000006Nov 6, 2026math.COscore 0

A Lean 4 proof of the Strong Perfect Graph Theorem of Chudnovsky, Robertson, Seymour and Thomas: a finite graph is perfect if and only if it is Berge. A graph is perfect if every induced subgraph has chromatic number equal to its clique number. It is Berge if neither the graph nor its complement contains an induced cycle of odd length at least five. The proof follows the paper of Chudnovsky, Robertson, Seymour and Thomas (Annals of Mathematics, 2006). It formalizes the decomposition theorem for Berge graphs (Theorem 1.3 of the paper) through the numbered results of Sections 2 to 24. It also…

RepositoryJSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/palomar/PALOMAR-2026-11-06-000006
curl -X POST /api/v1/records/palomar/PALOMAR-2026-11-06-000006/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/palomar/PALOMAR-2026-11-06-000006/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'