This chapter considers a new type of graph coloring known as edge coloring. It begins with a discussion of an idea by Scottish physicist Peter Guthrie Tait that led to edge coloring. Tait proved that the regions of every 3-regular bridgeless planar graph could be colored with four or fewer colors if and only if the edges of such a graph could be colored with three colors so that every two adjacent edges are colored differently. Tait thought that he had found a new way to solve the Four Color Problem. The chapter also examines the chromatic index of a graph, Vizing's Theorem, applications of edge colorings, and a class of numbers in graph theory called Ramsey numbers. Finally, it describes the Road Coloring Theorem which deals with traffic systems consisting only of one-way streets in which the same number of roads leave each location.
Princeton Scholarship Online requires a subscription or purchase to access the full text of books within the service. Public users can however freely search the site and view the abstracts and keywords for each book and chapter.
If you think you should have access to this title, please contact your librarian.
To troubleshoot, please check our FAQs , and if you can't find the answer there, please contact us.