ABSTRACT
The only graph colorings we have considered thus far have been vertex colorings and region colorings in the case of plane graphs. There is a third coloring, however, which we will discuss in this chapter: 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. We will see that the subject of edge colorings is closely related to matchings and factorizations and that this area has applications to problems of scheduling.
