chapter  17
28 Pages

Edge Colorings

The graph colorings that we have considered are vertex colorings in Chapters 14 and 15 and map colorings (region colorings of plane graphs) in Chapter 16. With the aid of matchings and 1-factors in Chapter 12, 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 will be our focus in the current chapter.