Efficiently four-coloring planar graphs

Neil Robertson, Daniel P. Sanders, Paul Douglas 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
Externally publishedYes
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

    Robertson, N., Sanders, D. P., Seymour, P. D., & Thomas, R. (1996). Efficiently four-coloring planar graphs. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing, STOC 1996 (pp. 571-575). (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. Part F129452). Association for Computing Machinery. https://doi.org/10.1145/237814.238005