Stiebitz M. Graph Edge Coloring: Vizing's Theorem and Goldberg's Conjecture

John Wiley, 2012. — 339 p.The Edge Color Problem (ECP) is to find the chromatic index χ'{G) of a given graph G, that is, the minimum number of colors needed to color the edges of G such that no two adjacent edges receive the same color. Edge coloring dates back to Peter Guthrie Tait's attempts around 1880 to prove the Four-Color Theorem. Tait observed that coloring the countries of a map (i.e., of a plane, cubic and bridgeless graph G) with four colors is equivalent to coloring the boundaries (i.e., the edges of G) with three colors. Tait claimed that it is easily proved by induction that such a graph G can indeed be edge-colored using three colors, i.e., that χ'(G)=3. The statement became known as Tait's Theorem, but remained unproved until the Four- Color Theorem was finally resolved. Twenty years after Tait's claim a discussion in a French journal about Tait's Theorem prompted Petersen to present his graph as an example showing that Tait's Theorem is false if the condition that G is planar is omitted.
Compared with vertex coloring, the theory of edge coloring has received less attention until relatively recently. However, much studied areas, such as map coloring, matching theory, factorization theory, Latin squares, and scheduling theory, all have strong connections to edge coloring.
The first monograph devoted to edge coloring, by Stanley Fiorini and Robin J. Wilson, appeared in 1977. It contains a stimulating and useful exposition. Like in many of the published papers on edge coloring, the book by Fiorini and Wilson deals mainly with edge colorings of simple graphs. When considering edge coloring theoretically, and also in connection with many scheduling problems, multigraphs, however, occur in a natural way, and multigraph edge coloring is a topic where further work needs to be done. One of the major unsolved problems on multigraphs is a conjecture (Conjecture 1.2 in Sect. 1.4) from around 1970 by Mark K. Goldberg, also posed independently by Paul D. Seymour. This monograph is an attempt to show the importance of this conjecture for both mathematical theory and algorithmics.Vizing Fans
Kierstead Paths
Simple Graphs and Line Graphs
Tashkinov Trees
Goldberg's Conjecture
Extreme Graphs
Generalized Edge Colorings of Graphs
Twenty Pretty Edge Coloring Conjectures
A: Vizing's Two Fundamental Papers
B: Fractional Edge Colorings