Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Bulletin of the American Mathematical Society
Bulletin of the American Mathematical Society
ISSN 1088-9485(online) ISSN 0273-0979(print)

Graph minor theory


Author: László Lovász
Journal: Bull. Amer. Math. Soc. 43 (2006), 75-86
MSC (2000): Primary 05C83
Published electronically: October 24, 2005
MathSciNet review: 2188176
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A monumental project in graph theory was recently completed. The project, started by Robertson and Seymour, and later joined by Thomas, led to entirely new concepts and a new way of looking at graph theory.

The motivating problem was Kuratowski's characterization of planar graphs, and a far-reaching generalization of this, conjectured by Wagner: If a class of graphs is minor-closed (i.e., it is closed under deleting and contracting edges), then it can be characterized by a finite number of excluded minors. The proof of this conjecture is based on a very general theorem about the structure of large graphs: If a minor-closed class of graphs does not contain all graphs, then every graph in it is glued together in a tree-like fashion from graphs that can almost be embedded in a fixed surface.

We describe the precise formulation of the main results and survey some of its applications to algorithmic and structural problems in graph theory.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Bulletin of the American Mathematical Society with MSC (2000): 05C83

Retrieve articles in all journals with MSC (2000): 05C83


Additional Information

László Lovász
Affiliation: Microsoft Research, Redmond, Washington 98052

DOI: http://dx.doi.org/10.1090/S0273-0979-05-01088-8
PII: S 0273-0979(05)01088-8
Received by editor(s): June 6, 2005
Received by editor(s) in revised form: August 9, 2005
Published electronically: October 24, 2005
Additional Notes: This article is based on a lecture presented January 7, 2005, at the AMS Special Session on Current Events, Joint Mathematics Meetings, Atlanta, GA.
Article copyright: © Copyright 2005 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.