Efficiently four-coloring planar graphs

Neil Robertson, Daniel P. Sanders, Paul Seymour, Robin Thomas

Research output: Chapter in Book/Report/Conference proceedingConference contribution

70 Scopus citations

Abstract

An outline of a quadratic algorithm to 4-color planar graphs is presented, based upon a new proof of the Four Color Theorem. This algorithm improves a quartic algorithm of Appel and Haken.

Original languageEnglish (US)
Title of host publicationProceedings of the 28th Annual ACM Symposium on Theory of Computing, STOC 1996
PublisherAssociation for Computing Machinery
Pages571-575
Number of pages5
ISBN (Electronic)0897917855
DOIs
StatePublished - Jul 1 1996
Event28th Annual ACM Symposium on Theory of Computing, STOC 1996 - Philadelphia, United States
Duration: May 22 1996May 24 1996

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
VolumePart F129452
ISSN (Print)0737-8017

Other

Other28th Annual ACM Symposium on Theory of Computing, STOC 1996
CountryUnited States
CityPhiladelphia
Period5/22/965/24/96

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint Dive into the research topics of 'Efficiently four-coloring planar graphs'. Together they form a unique fingerprint.

Cite this