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).