{"id":"palomar/PALOMAR-2026-11-06-000006","url":"https://github.com/mahdi-jfri/StrongPerfectGraphTheorem/tree/f81220fa3d8ebf987d44ab452f3abadb13c0ac2d","json":"https://data.palomar-registry.org/entries/PALOMAR-2026-11-06-000006-v1.json","repo":"https://github.com/mahdi-jfri/StrongPerfectGraphTheorem","tags":["math.CO","cs.DM","msc:05C17","msc:05C75","msc:05C15","msc:05C69","msc:05C76"],"score":0,"title":"The Strong Perfect Graph Theorem","trust":"high","domain":"math.CO","source":"palomar","authors":["Arshia Soltani Moakhar","Iman Gholami","Max Springer","Mahdi JafariRaviz","MohammadTaghi Hajiaghayi"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"verified":true,"discussed":0,"published":"2026-11-06","reactions":{},"formalized":true,"formalizes":[{"title":"The strong perfect graph theorem","identifier":"doi:10.4007/annals.2006.164.51","relationship":"formalizes"}]}