Edge Coloring & Vizing's Theorem

Proper edge colorings, the chromatic index, and the class 1 / class 2 dichotomy.

The idea

Theorem (Vizing's theorem).

Let $G$ be a simple graph — no loops and no repeated edges — with largest vertex degree $\Delta(G)$, and let $\chi'(G)$ be the smallest number of colors in a proper edge coloring of $G$, one in which any two edges sharing a vertex receive different colors. Then $\Delta(G) \le \chi'(G) \le \Delta(G) + 1.$

An edge coloring of $G$ assigns a color to each edge, and it is proper when any two edges that meet at a common vertex receive different colors. The chromatic index $\chi'(G)$ is the smallest number of colors a proper edge coloring of $G$ can use. It is the edge counterpart of vertex coloring, where adjacent vertices are the ones required to differ.

The lower bound is the easy half. The content of the theorem is the upper bound: one extra color always suffices. So $\chi'(G)$ takes one of exactly two values, where vertex coloring admits no such squeeze. Graphs with $\chi'(G) = \Delta(G)$ are class 1, and graphs with $\chi'(G) = \Delta(G) + 1$ are class 2. The theorem does not decide between the two, and determining the class of a given graph is a genuinely hard problem.

Ways to work on it

• Walkthrough. Proper edge colorings and Vizing's two-value bound on the number of colors needed.
• Practice. Read off Vizing's candidate values from the maximum degree.
• Hardest. Determine the exact chromatic index, not just Vizing's two candidates.

Not sure where to start? Take the ten-question placement test.