Coloring Graphs
Arthur T. Benjamin, Gary Chartrand, Ping Zhang · Princeton University Press eBooks · 2017
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.