Chapter 1 Introduction One of the major areas Of all these colorings.the most studied and most popular graph colorings are the vertex colorings.These colorings came about through coloring the regions of planar graphs,that is,through coloring the regions of maps.In this chapter.we review some fundamental concepts and results on vertex and edge colorings that will be encountered as we proceed.In addition,we review some facts concerning degrees of vertices in graphs.outdegre s and inde es of vertices sin digraphs as Euleria dis tic is mentioned that will b e encountered often.We refer to the book [15]for graph theory notation and terminology not described here. 1.1 Graph Colorings of whether the re every lored ith four or fe t every tw aving a be ary lin n are colore differently blem has a le ngthy and col orful history (see 75).While a solution to this problem would not be found until 1976,there were many attempts to solve it by many individuals during its 124-vear history.A famous incorrect (although interesting)argument was made by the British lawyer and mathematician Alfred Bray Kempe in 1879.Kempe observed that coloring the regions of maps so that"adjacent regions"are colored differently was the same problem as coloring rtain diagrams so that two points ined by a line are colore g the vertices of a planar graph so that adjacent vertices ar colored differently) The Author 2016 P.Zhang,A Kaleic Chapter 1 Introduction One of the major areas within graph theory is that of colorings, namely region colorings of graphs embedded on surfaces, vertex colorings and edge colorings. Of all these colorings, the most studied and most popular graph colorings are the vertex colorings. These colorings came about through coloring the regions of planar graphs, that is, through coloring the regions of maps. In this chapter, we review some fundamental concepts and results on vertex and edge colorings that will be encountered as we proceed. In addition, we review some facts concerning degrees of vertices in graphs, outdegrees and indegrees of vertices in digraphs as well as Eulerian graphs and digraphs. Finally, a fundamental fact from discrete mathematics is mentioned that will be encountered often. We refer to the book [15] for graph theory notation and terminology not described here. 1.1 Graph Colorings It was 1852 when the young British scholar Francis Guthrie brought up the question of whether the regions of every map could be colored with four or fewer colors so that every two regions having a boundary line in common are colored differently. This Four Color Problem has a lengthy and colorful history (see [75]). While a solution to this problem would not be found until 1976, there were many attempts to solve it by many individuals during its 124-year history. A famous incorrect (although interesting) argument was made by the British lawyer and mathematician Alfred Bray Kempe in 1879. Kempe observed that coloring the regions of maps so that “adjacent regions” are colored differently was the same problem as coloring the points of certain diagrams so that two points joined by a line are colored differently (coloring the vertices of a planar graph so that adjacent vertices are colored differently). © The Author 2016 P. Zhang, A Kaleidoscopic View of Graph Colorings, SpringerBriefs in Mathematics, DOI 10.1007/978-3-319-30518-9_1 1