For well over a century, the most famous unsolved problem in graph theory, and one of the most famous unsolved problems in mathematics, was a map coloring problem called the Four Color Problem. This problem, dealing with determining whether a conjecture called the Four Color Conjecture was true or false, had a major impact on the development of graph theory. This problem will be discussed in the current chapter as will related coloring problems dealing with graphs that are embeddable on certain surfaces.