Maria Chudnovsky

Professor of Mathematics at Princeton & Proof of Strong Perfect Graph Theorem

Lifespan 1977–

Technical Depth advanced

Key Breakthrough Proof of the Strong Perfect Graph Theorem (2002) & Claw-Free Decomposition

Focus Areas

graph theory discrete mathematics combinatorial algorithms

Topic Keywords

#graph-theory #discrete-math #algorithms #macarthur-fellow #combinatorics

Source: Historical Biographical Archive / Wikimedia Commons

Maria Chudnovsky

Professor of Mathematics at Princeton & Proof of Strong Perfect Graph Theorem

Biographical Overview

MacArthur "Genius" Fellow and Professor of Mathematics at Princeton University. In 2002, with Robertson, Seymour, and Thomas, Chudnovsky proved Claude Berge's 40-year-old Strong Perfect Graph Conjecture, resolving one of the most celebrated open problems in discrete mathematics and theoretical computer science.

"When you work on a problem for years, you build an intuition for the hidden geometry of the graph that cannot be explained in a single equation."
— Maria Chudnovsky

Lifespan 1977–

Technical Depth advanced

Key Breakthrough Proof of the Strong Perfect Graph Theorem (2002) & Claw-Free Decomposition

Focus Areas

graph theory discrete mathematics combinatorial algorithms

Topic Keywords

#graph-theory #discrete-math #algorithms #macarthur-fellow #combinatorics

Source: Historical Biographical Archive / Wikimedia Commons

💡

Historical Context & Impact

In short

Claude Berge proposed the Strong Perfect Graph Conjecture in 1961, and for forty years it baffled the world's greatest mathematicians and computer scientists. As a graduate student at Princeton in her twenties, Chudnovsky co-authored the 178-page landmark proof that finally solved it, earning the Fulkerson Prize.

Key Technical Breakthroughs & Inventions

Proof of the Strong Perfect Graph Theorem (2002) Co-authored the 178-page proof proving that a graph is perfect if and only if neither it nor its complement contains an odd cycle of length at least 5 as an induced subgraph.

Polynomial-Time Recognition of Perfect Graphs Developed an O(n^9) polynomial-time recognition algorithm for perfect graphs, linking structural graph theory with efficient optimization.

Structure of Claw-Free Graphs Established comprehensive structural decomposition theorems for claw-free graphs, solving longstanding open questions in combinatorial optimization.

Graph Coloring and Maximum Clique Bounds Proved fundamental chromatic number bounds and polynomial-time coloring algorithms for broad graph classes.