Article Free Access Share on Efficiently four-coloring planar graphs Authors: Neil Robertson Department of Mathematics, The Ohio State University, Columbus, Ohio Department of Mathematics, The Ohio State University, Columbus, OhioView Profile , Daniel P. Sanders Department of Mathematics, The Ohio State University, Columbus, Ohio Department of Mathematics, The Ohio State University, Columbus, OhioView Profile , Paul Seymour Bellcore, 445 South Street, Morristown, New Jersey Bellcore, 445 South Street, Morristown, New JerseyView Profile , Robin Thomas School of Mathematics, Georgia Institute of Technology, Atlanta, Georgia School of Mathematics, Georgia Institute of Technology, Atlanta, GeorgiaView Profile Authors Info & Claims STOC '96: Proceedings of the twenty-eighth annual ACM symposium on Theory of ComputingJuly 1996 Pages 571–575https://doi.org/10.1145/237814.238005Published:01 July 1996Publication History 63citation2,172DownloadsMetricsTotal Citations63Total Downloads2,172Last 12 Months487Last 6 weeks60 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A graph G has tree-width at most k if the vertices of G can be decomposed into a tree-like structure of sets of vertices, each set having cardinality at most $k + 1$. An alternate definition of tree-width is stated in terms of a k-elimination sequence, which is an order to eliminate the vertices of the graph such that each vertex, at the time it is eliminated from the graph, has degree at most k. Arnborg and Proskurowski showed that if a graph has tree-width at most a fixed k, then many NP-hard problems can be solved in linear time, provided this k-elimination sequence is part of the input. These algorithms are very efficient for small k, such as 2, 3, or 4, but may be impractical for large k as they depend exponentially on k. A reduction process is developed, and reductions are shown that can be applied to a graph of tree-width at most four without increasing its tree-width. Further, each graph of tree-width at most four contains one of these reductions. The reductions are then used in a linear-time algorithm that generates a 4-elimination sequence, if one exists.