Chapter 1 Introduction One of the most popular areas of study in graph theory is colorings.This topic can be traced back to the origin of the Four Color Problen and whether it is possible to color the egions of every map with four or fewe two regions having a common b Later it was seen that this problem could be looked at as a problem in graph theory- whethe it is always possible to color the regions of every planar graph (embedded in the plane)so that every two adjacent regions are colored differently.It became known that the Four Color Problem could be solved if it could be solved for all bridgeless cubic planar graphs. 1.1 The Origin of Edge Colorings The Scottish mathematician Tait [76]discovered a unique approach to solve the Four Color Problem.He proved that the edges of a bridgeless cubic planar graph G can be colored with three colors so that every two adjacent edges are colored differently if and only if the regions of G can be colored with four colors so that every two adjacent eareiferey Although Tait's approach ever edtoa solution of the Four Color Problem,he such a 3-coloring of p jo AltEAsps s of G induce an approp e ns of G.The al of induce,in a number of ways,vertex colorings possessing desirable properties. Colors can be objects of any type.While initially,the colors that were used to color the regions of maps were actual colors such as red,blue,green and so on,later it became common to use positive integers for colors as these were simpler and it was easier to keep track of the number of colors being used.Later yet,elements of Zk.the integers modulo k,for somek2.were sometimes used as colors.Subsets or multisets of some set were also used as c lors.Originally,the only requirem Ping Zhang 2015 orings.SpringerBriefs in Mathematics.Chapter 1 Introduction One of the most popular areas of study in graph theory is colorings. This topic can be traced back to the origin of the Four Color Problem and whether it is possible to color the regions of every map with four or fewer colors in such a way that every two regions having a common boundary are assigned different colors. Later it was seen that this problem could be looked at as a problem in graph theory—whether it is always possible to color the regions of every planar graph (embedded in the plane) so that every two adjacent regions are colored differently. It became known that the Four Color Problem could be solved if it could be solved for all bridgeless cubic planar graphs. 1.1 The Origin of Edge Colorings The Scottish mathematician Tait [76] discovered a unique approach to solve the Four Color Problem. He proved that the edges of a bridgeless cubic planar graph G can be colored with three colors so that every two adjacent edges are colored differently if and only if the regions of G can be colored with four colors so that every two adjacent regions are colored differently. Although Tait’s approach never led to a solution of the Four Color Problem, he was able to prove that such a 3-coloring of the edges of G induce an appropriate 4-coloring of the regions of G. The goal of this book is to describe a variety of edge colorings that have been introduced which induce, in a number of ways, vertex colorings possessing desirable properties. Colors can be objects of any type. While initially, the colors that were used to color the regions of maps were actual colors such as red, blue, green and so on, later it became common to use positive integers for colors as these were simpler and it was easier to keep track of the number of colors being used. Later yet, elements of Zk, the integers modulo k, for some k 2, were sometimes used as colors. Subsets or multisets of some set were also used as colors. Originally, the only requirement © Ping Zhang 2015 P. Zhang, Color-Induced Graph Colorings, SpringerBriefs in Mathematics, DOI 10.1007/978-3-319-20394-2_1 1