ABSTRACT
This chapter explores graph coloring, a strategy often used to model resource restrictions. But before one can get into the heart of this graph model, which begins with a historically significant problem, known as the Four Color Theorem. The Four Color Conjecture started as a map coloring problem, yet migrated into a graph coloring problem. In the late 19th century, Alfred Kempe studied the dual problem where each region on a map was represented by a vertex and an edge exists between two vertices if their corresponding regions share a border. This approach was extensively used in the mid-20th century as the study of graph theory exploded with the advent of the computer. The chapter explores graph colorings for graphs that may or may not be planar, mainly since one may know that planar graphs need at most 4 colors and so there is not much room for further exploration.
