Efficiently four-coloring planar graphs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficiently four-coloring planar graphs

Full text

Pdf (491 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-eighth annual ACM symposium on Theory of computing table of contents

Philadelphia, Pennsylvania, United States

Pages: 571 - 575

Year of Publication: 1996

ISBN:0-89791-785-5

Authors

Neil Robertson	Department of Mathematics, The Ohio State University, Columbus, Ohio
Daniel P. Sanders	Department of Mathematics, The Ohio State University, Columbus, Ohio
Paul Seymour	Bellcore, 445 South Street, Morristown, New Jersey
Robin Thomas	School of Mathematics, Georgia Institute of Technology, Atlanta, Georgia

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 12, Downloads (12 Months): 114, Citation Count: 6

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/237814.238005 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	K. Appel and W. Haken, Every planar map is four colorable, Contemp. Math. 98 (1989) 1-741.
	2	A. Bernhart, Six rings in minimal five color maps, Amer. d. Math. 69 (1947) 391-412.
	3	G.D. Birkhoff, The reducibility of maps, Amer. J. Math. 35 (1913) 114-128.
	4	N. Chiba, T. Nishizeki, and N. Saito, A linear 5- coloring algorithm of planar graphs, J. Algorithms 2 (1981)317-327.
	5	M.R. Garey, D.S. Johnson, and L.J. Stockmeyer, Some simplified NP-complete graph problems, Theoret. Comput. $ci. 1 (1976) 237-267.
	6	P.J. Heawood, Map colour theorem, Quart. J. Pure App1. Math. 24 (1890) 332-338.
	7	H. Heesch, Untersuchungen zum Vierfarbenproblem, Hochschutskriptum 810 / a / b, Bibliographisches Instit/it, Mannheim 1969.
	8	N. Robertson, D.P. Sanders, P.D. Seymour, and R. Thomas, The four colour theorem, submitted.
	9	Carsten Thomassen, Every planar graph is 5-choosable, Journal of Combinatorial Theory Series B, v.62 n.1, p.180-181, Sept. 1994 [doi>10.1006/jctb.1994.1062]
	10	P. Wernicke, /Jber den kartographischen Vierfarbensatz, Math. Ann., 58 (1904) 413-426.

CITED BY 6

	L. J. Cowen , W. Goddard , C. E. Jesurum, Coloring with defect, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.548-557, January 05-07, 1997, New Orleans, Louisiana, United States
	Jack Snoeyink , Marc van Kreveld, Good orders for incremental (re)construction, Proceedings of the thirteenth annual symposium on Computational geometry, p.400-402, June 04-06, 1997, Nice, France
	Jochen Alber , Henning Fernau , Rolf Niedermeier, Graph separators: a parameterized view, Journal of Computer and System Sciences, v.67 n.4, p.808-832, December 2003
	Jochen Alber , Henning Fernau , Rolf Niedermeier, Parameterized complexity: exponential speed-up for planar graph problems, Journal of Algorithms, v.52 n.1, p.26-56, July 2004
	Robert Freimer, Generalized map coloring for use in geographical information systems, Proceedings of the 8th ACM international symposium on Advances in geographic information systems, p.167-173, November 06-11, 2000, Washington, D.C., United States
	Juha-Matti Koljonen , Matti Peltomäki , Mikko Alava , Olav Tirkkonen, Inertia-based distributed channel allocation, Proceedings of the 2009 International Conference on Wireless Communications and Mobile Computing: Connecting the World Wirelessly, June 21-24, 2009, Leipzig, Germany