In this BSc thesis we deal with chromatic index of cubic graphs, where we mainly focus on a significant part of the family of graphs, named generalized Petersen graphs. A graph Γ is said to be k-edge-colorable, if we can color its edges with k colors, so that incident edges are colored with different colors. The smallest such number k is called the chromatic index and it is denoted by χ'(Γ). Due to the fact that generalized Petersen graphs are cubic graphs, Vizing's theorem implies that their chromatic index is either 3 or 4. The results of this BSc thesis represent an important part of the proof, that the famous Petersen graph is the only generalized Petersen graph, which is not 3-edge colorable. In other words, the Petersen graph GP(5,2) is the only generalized Petersen graph, whose chromatic index equals 4.
|
