News FocusMathematics

Graph Theory Uncovers the Roots of Perfection

See allHide authors and affiliations

Science  05 Jul 2002:
Vol. 297, Issue 5578, pp. 38
DOI: 10.1126/science.297.5578.38

You are currently viewing the summary.

View Full Text

Log in to view the full text

Log in through your institution

Log in through your institution


The so-called strong perfect graph conjecture (SPGC) might enable mathematicians to quickly identify perfect graphs, which have properties that make otherwise intractable problems involving networks easy to solve. Now if four graph theorists' proof of the SPGC holds up, they will reap a $10,000 bounty.