chapter  11
Edge Colorings
Pages 46

The graph colorings that we have considered are vertex colorings in Chapter 8 and map colorings (region colorings of plane graphs) in Chapter 9. With the aid of matchings and 1-factors in Chapter 10, we now consider a third coloring, namely edge colorings. As with vertex colorings where the primary emphasis has been on proper vertex colorings, the customary requirement for edge colorings is that adjacent edges be colored differently, resulting in proper edge colorings. This too will be our focus in the current chapter.