Jump to ContentJump to Main Navigation
The Fascinating World of Graph Theory$
Users without a subscription are not able to see the full content.

Ping Zhang, Gary Chartrand, and Arthur Benjamin

Print publication date: 2017

Print ISBN-13: 9780691175638

Published to Princeton Scholarship Online: May 2018

DOI: 10.23943/princeton/9780691175638.001.0001

Show Summary Details
Page of

PRINTED FROM PRINCETON SCHOLARSHIP ONLINE (www.princeton.universitypressscholarship.com). (c) Copyright Princeton University Press, 2020. All Rights Reserved. An individual user may print out a PDF of a single chapter of a monograph in PRSO for personal use.date: 04 June 2020

Coloring Graphs

Coloring Graphs

(p.206) 11 Coloring Graphs
The Fascinating World of Graph Theory

Arthur Benjamin

Gary Chartrand

Ping Zhang

Princeton University Press

This chapter considers the concept of coloring the vertices of a graph by focusing on the Four Color Problem. It begins with a discussion of three mathematics problems that involve conjecture, attributed to Pierre Fermat, Leonhard Euler, and Christian Goldbach. It then examines one of the most famous problems in mathematics, the Four Color Problem, which addresses the question of whether it is always possible to color the regions of every map with four colors so that neighboring regions are colored differently. After an overview of the origins of the Four Color Problem, the chapter goes on to analyze the Four Color Conjecture, Alfred Bray Kempe's proof of the Four Color Conjecture, and the Five Color Theorem. Finally, it looks at the Four Color Problem in the twentieth century, along with vertex colorings and their applications.

Keywords:   graph, coloring, Four Color Problem, Pierre Fermat, Leonhard Euler, Christian Goldbach, Four Color Conjecture, Alfred Bray Kempe, Five Color Theorem, vertex coloring

Princeton Scholarship Online requires a subscription or purchase to access the full text of books within the service. Public users can however freely search the site and view the abstracts and keywords for each book and chapter.

Please, subscribe or login to access full text content.

If you think you should have access to this title, please contact your librarian.

To troubleshoot, please check our FAQs , and if you can't find the answer there, please contact us.