CSDS 455: Applied Graph Theory
Homework 13
Problem 1: In edge coloring, we assign colors to the edges of G so that all the edges incident to a vertex
receive different colors. χ
0
(G) is the minimum number of colors required to edge color G.
Assume χ
0
(G) > ∆(G)+ 1 but for any edge xy, χ
0
(G−xy) = ∆+ 1. Prove that in every proper edge coloring
of G − xy there exists a path from x to y in which the edges alternate between two colors.
(We can use this fact to prove Vizing’s Theorem: χ
0
(G) ≤ ∆(G) + 1 by induction.)
Problem 2: Assume G is a ∆-regular multigraph, and assume ∆ is even. Prove that χ
0
(G) ≤
3
2∆(G).
