40.04.07 · combinatorics / graph-theory-core

Edge Colouring and List Colouring: Vizing's Theorem and Choosability

shipped3 tiersLean: none

Anchor (Master): Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) Ch. 5 §5.3-§5.4 (edge colouring, Vizing, list colouring, Galvin's theorem, the list-colouring conjecture) and §5.4 with Thomassen's 5-choosability of planar graphs; Bondy-Murty 2008 §17 (edge and list colouring); the original sources Vizing 1964, König 1916, Galvin 1995, Thomassen 1994, Alon-Tarsi 1992 and Alon 1999 (the Combinatorial Nullstellensatz)

Intuition Beginner

In the last unit you coloured the dots of a graph so that joined dots differed. Now colour the lines instead. The rule flips to the lines: two lines that share an endpoint must get different colours. Think of a sports league where every team must play every other team. Each game is a line between two teams, and a colour is a time slot. Two games that share a team cannot run at the same time, because a team cannot be in two places at once. The fewest time slots you need is the fewest line-colours, and that count is the star of this unit.

How many colours could you possibly need? Look at the busiest dot — the one touching the most lines, say $Δ$ of them. Those $Δ$ lines all meet at that dot, so they all clash with one another and each needs its own colour. You can never finish with fewer than $Δ$ colours. The surprise, proved by Vizing, is that you almost never need many more: $Δ$ or $Δ + 1$ colours always suffice, never more. The whole world of line-colouring splits into two narrow classes, those needing exactly $Δ$ and those needing one extra.

A second twist is list-colouring. Instead of one shared palette, each dot or line is handed its own short list of allowed colours, perhaps different lists. Can you still finish if every list is as long as the number you would normally need? For dots the answer can be no, the lists can be cruel. For lines of certain graphs the answer is a clean yes.

Visual Beginner

Picture four teams $A, B, C, D$ , every pair playing once: six games in all. Draw a dot per team and a line per game. Each team plays the other three, so every dot touches three lines and the busiest count is $Δ = 3$ . You want three time slots so no team plays twice at once.

The trick: the six games split into three pairs of "opposite" games that share no team, and each pair gets one slot. Game $A B$ and game $C D$ share nobody, so both play in slot red. Likewise $A C$ with $B D$ in blue, and $A D$ with $B C$ in green. Every team plays once per slot.

game	teams	slot
AB	A, B	red
CD	C, D	red
AC	A, C	blue
BD	B, D	blue
AD	A, D	green
BC	B, C	green

Three slots finish the round-robin, matching $Δ = 3$ . This graph is one of the lucky ones needing exactly the busiest-dot count, no extra.

Worked example Beginner

Edge-colour a five-team round-robin, every pair playing once, using as few slots as possible. Now there are five teams $1, 2, 3, 4, 5$ and ten games, and each team plays four others, so the busiest count is $Δ = 4$ .

Step 1. Try four slots. With five teams, in any single slot a team either plays or sits out, and games in one slot pair up disjoint teams. Five teams cannot all be paired at once — one always sits out — so each slot holds at most two games. Four slots would cover at most eight games, but there are ten.

Step 2. Count the floor again. Ten games, at most two per slot, needs at least five slots. So four slots cannot work here even though the busiest count is four.

Step 3. Build five slots. Seat the teams in a pentagon and rotate. Slot 1: games $2 - 5$ and $3 - 4$ (team $1$ rests). Slot 2: $3 - 1$ and $4 - 5$ (team $2$ rests). Slot 3: $4 - 2$ and $5 - 1$ (team $3$ rests). Slot 4: $5 - 3$ and $1 - 2$ (team $4$ rests). Slot 5: $1 - 4$ and $2 - 3$ (team $5$ rests). All ten games appear once and no team plays twice in a slot.

Step 4. Read off the count. Five slots are needed and five suffice, which is $Δ + 1 = 5$ , one more than the busiest count.

What this tells us: an odd round-robin needs one extra slot beyond $Δ$ , because somebody always rests. This is a "class-two" graph in Vizing's split. The four-team case sat in class one; the five-team case sits in class two — and Vizing promises those are the only two possibilities.

Check your understanding Beginner

Formal definition Intermediate+

Let $G = (V, E)$ be a graph as in 40.04.01. A proper edge colouring with $k$ colours is a map $c : E \to {1, \dots, k}$ with $c (e) \neq = c (f)$ whenever $e$ and $f$ share an endpoint ^{[Diestel 2017 §5.3]}. The chromatic index (or edge-chromatic number) $χ^{'} (G)$ is the least such $k$ . Equivalently, a colour class is a matching (a set of pairwise non-adjacent edges), so $χ^{'} (G)$ is the least number of matchings partitioning $E$ . Since the $Δ (G)$ edges at a maximum-degree vertex pairwise share that vertex, they need distinct colours, giving the lower bound $χ^{'} (G) \geq Δ (G)$ .

The line graph $L (G)$ has vertex set $E (G)$ , with two edges of $G$ adjacent in $L (G)$ exactly when they share an endpoint. A proper edge colouring of $G$ is precisely a proper vertex colouring of $L (G)$ , so $χ^{'} (G) = χ (L (G))$ in the sense of 40.04.06; edge colouring is vertex colouring transported through the line-graph functor, though $L (G)$ can have much larger maximum degree than $G$ , so Brooks' bound on $L (G)$ does not by itself give Vizing's.

A list assignment $L$ gives each vertex $v$ a set $L (v)$ of permitted colours; an $L$ -colouring is a proper colouring $c$ with $c (v) \in L (v)$ for all $v$ . A graph is $k$ -choosable if it admits an $L$ -colouring for every assignment with $∣ L (v) ∣ \geq k$ for all $v$ . The list chromatic number (or choosability) $ch (G)$ is the least such $k$ . The list chromatic index $ch^{'} (G)$ is the analogue for edges: assign each edge $e$ a list $L (e)$ and ask for a proper edge colouring with $c (e) \in L (e)$ . Because an ordinary colouring is the special case where all lists equal ${1, \dots, k}$ , one always has $ch (G) \geq χ (G)$ and $ch^{'} (G) \geq χ^{'} (G)$ .

A graph is class 1 if $χ^{'} (G) = Δ (G)$ and class 2 if $χ^{'} (G) = Δ (G) + 1$ ; Vizing's theorem (below) shows these exhaust the possibilities. A kernel of a directed graph $D$ is an independent set $K$ of vertices such that every vertex outside $K$ has an out-neighbour in $K$ ; an orientation is kernel-perfect if every induced subdigraph has a kernel. Kernels drive Galvin's list-edge-colouring theorem.

Counterexamples to common slips

$ch (G) = χ (G)$ fails badly. The complete bipartite graph $K_{k, k}$ has $χ = 2$ but $ch (K_{k, k}) \to \infty$ as $k \to \infty$ ; with $k = (t 2 t - 1)$ one can force $ch > t$ . Two-colourability does not bound choosability.
Brooks for $L (G)$ does not give Vizing. The line graph of a graph with maximum degree $Δ$ can have maximum degree up to $2Δ - 2$ , so $χ (L (G)) \leq 2Δ - 2$ from the degree bound is far weaker than $χ^{'} \leq Δ + 1$ . Vizing's gain over the naive line-graph bound is the whole content of the fan argument.
Class membership is not read off from $Δ$ alone. The complete graph $K_{n}$ is class 1 for even $n$ and class 2 for odd $n \geq 3$ ; the Petersen graph is class 2 with $Δ = 3$ . Deciding class is NP-hard in general (Holyer), so no simple degree criterion settles it.
A matching colour class need not be perfect. Colour classes in an edge colouring are matchings, but they may miss vertices; only the regular class-1 case forces each class to be a perfect matching (a $1$ -factor).

Key theorem with proof Intermediate+

Theorem (Vizing 1964). For every (simple) graph $G$ , $Δ (G) \leq χ^{'} (G) \leq Δ (G) + 1$ . (See ^{[Vizing 1964]}, ^{[Diestel 2017 §5.3]}, ^{[Bondy-Murty 2008 §17.2]}.)

Proof. The lower bound is the degree count above. For the upper bound, set $Δ = Δ (G)$ and use the palette ${1, \dots, Δ + 1}$ . We show by induction on $∣ E ∣$ that $G$ has a proper edge colouring with these $Δ + 1$ colours; the empty graph is coloured. Take an edge $e_{0} = v u_{0}$ and, by induction, properly colour $G - e_{0}$ with $Δ + 1$ colours. We extend the colouring to $e_{0}$ .

At each vertex $w$ , at most $Δ$ colours appear on its incident coloured edges, so since the palette has $Δ + 1$ colours, every vertex misses at least one colour: a colour absent from all edges at $w$ . Build a fan at $v$ : a maximal sequence of distinct neighbours $u_{0}, u_{1}, \dots, u_{k}$ of $v$ such that for each $i \geq 1$ , the edge $v u_{i}$ is coloured with a colour missing at $u_{i - 1}$ . Let $α$ be a colour missing at $v$ and $β_{i}$ a colour missing at $u_{i}$ .

If some $u_{i}$ misses a colour also missing at $v$ (a common missing colour $γ$ ), recolour by shifting the fan: for $j = i, i - 1, \dots, 1$ set $c (v u_{j}) := c (v u_{j + 1})$ (with $c (v u_{i})$ vacated by giving it $γ$ ), and colour $e_{0} = v u_{0}$ by the appropriate freed colour; concretely, give each $v u_{j}$ the colour previously on $v u_{j + 1}$ down to $v u_{1}$ , then colour $v u_{0}$ with $α$ . This is proper because each reassigned colour was missing at the relevant $u_{j - 1}$ , and $γ$ is missing at both ends of $v u_{i}$ . The colouring now covers $e_{0}$ .

Otherwise no $u_{i}$ shares a missing colour with $v$ . Let $β = β_{k}$ be missing at the last fan vertex $u_{k}$ and $α$ be missing at $v$ ; by maximality $α \neq = β$ and the colour $β$ appears at $v$ on some fan edge $v u_{j}$ . Consider the Kempe chain $P$ : the maximal alternating $α$ / $β$ path starting at $v$ . Because every vertex misses at most a controlled set of colours, $P$ ends at a vertex distinct from at least one of $u_{j}, u_{k}$ ; swap the colours $α \leftrightarrow β$ along $P$ . After the swap, the colour $α$ becomes missing at the fan vertex whose subfan can now be shifted as in the first case, and shifting that subfan frees a colour for $e_{0}$ . Either branch extends the colouring to $e_{0}$ , completing the induction. $□$

Bridge. Vizing's theorem builds toward the entire edge- and list-colouring theory and appears again in König's bipartite refinement and in Galvin's list version, because it pins the chromatic index to the maximum degree exactly as Brooks pinned the chromatic number to it in 40.04.06 — this is exactly the degree-and-obstruction pattern of that unit, now read on edges. The foundational reason the fan argument works is the surplus colour: with $Δ + 1$ colours every vertex misses one, and the fan plus Kempe chain are the bookkeeping that routes a missing colour to the uncoloured edge. Vizing's split into class 1 and class 2 generalises Brooks' clique/odd-cycle dichotomy, and the bridge is the line graph: $χ^{'} (G) = χ (L (G))$ puts edge colouring inside vertex colouring, while the fan argument supplies the bound that the naive line-graph degree could not. Putting these together, the chromatic index sits between two consecutive integers, and the class question — which integer — becomes the central insight organising the rest of the unit.

Exercises Intermediate+

Exercise 4 (medium, short-answer).

Prove that every bipartite graph $G$ satisfies $χ^{'} (G) = Δ (G)$ (König's edge-colouring theorem), via the line graph or directly.

Hint

Induct on edges: remove a maximum-degree vertex's incident edge, or use that a bipartite graph with maximum degree $Δ$ embeds into a $Δ$ -regular bipartite graph, which has a perfect matching by Hall.

Answer

Embed $G$ into a $Δ$ -regular bipartite graph $H$ by adding vertices and edges to raise every degree to $Δ$ (each side can be padded to equal size, then degrees lifted using that a bipartite graph with maximum degree $Δ$ extends to a $Δ$ -regular one). A $Δ$ -regular bipartite graph has a perfect matching by Hall's theorem 40.04.02, since every vertex subset $S$ on one side spans $Δ∣ S ∣$ edge-endpoints, forcing $∣ N (S) ∣ \geq ∣ S ∣$ . Remove this perfect matching as colour class $1$ ; the rest is $(Δ - 1)$ -regular bipartite, and induction colours it with $Δ - 1$ further colours. So $χ^{'} (H) = Δ$ , and restricting to $G$ gives $χ^{'} (G) \leq Δ$ ; with $χ^{'} \geq Δ$ always, equality holds. Rubric: full credit for the regular embedding, the Hall/perfect-matching extraction, and the induction down the degrees.

Exercise 5 (medium, short-answer).

Show that the Petersen graph is class 2, i.e. $χ^{'} (Petersen) = 4$ while $Δ = 3$ .

Hint

A $3$ -edge-colouring of a cubic graph would partition the edges into three perfect matchings; show the Petersen graph has no such partition (it has no proper $3$ -edge-colouring, equivalently no Tait colouring).

Answer

The Petersen graph is $3$ -regular with $15$ edges. A proper $3$ -edge-colouring would split the edge set into three perfect matchings, each of size $5$ . The Petersen graph has perfect matchings, but no two disjoint perfect matchings whose complement is again a perfect matching: removing any perfect matching leaves a $2$ -regular graph that is a union of cycles, and in the Petersen graph that union always contains an odd cycle (two $5$ -cycles), which is not $2$ -edge-colourable. Hence no $3$ -edge-colouring exists, so $χ^{'} \geq 4$ ; Vizing gives $χ^{'} \leq Δ + 1 = 4$ , so $χ^{'} = 4$ . Rubric: full credit for reducing to three perfect matchings and exhibiting the odd-cycle obstruction (the two $5$ -cycles).

Exercise 7 (hard, short-answer).

Prove that $ch (K_{k, k}) > t$ for $k = (t 2 t - 1)$ , exhibiting a bipartite graph whose choosability exceeds its chromatic number $2$ by an arbitrary amount.

Hint

Use colour set ${1, \dots, 2 t - 1}$ . On each side, index the vertices by the $t$ -subsets of ${1, \dots, 2 t - 1}$ and give each vertex the list equal to its subset. Show any $L$ -colouring forces a colour used on both sides at adjacent vertices.

Answer

Take colours ${1, \dots, 2 t - 1}$ . The left part $A$ and right part $B$ each have $(t 2 t - 1)$ vertices, indexed by the $t$ -element subsets of ${1, \dots, 2 t - 1}$ ; give vertex $S$ the list $L (S) = S$ (size $t$ ). Suppose an $L$ -colouring exists. Let $C_{A} \subseteq {1, \dots, 2 t - 1}$ be the set of colours used on $A$ and $C_{B}$ on $B$ . If some colour $c \in C_{A} \cap C_{B}$ , say $c$ colours $a \in A$ and $b \in B$ , then since $K_{k, k}$ joins every $A$ -vertex to every $B$ -vertex, $a$ and $b$ are adjacent and share colour $c$ — improper. So $C_{A}$ and $C_{B}$ are disjoint subsets of a $(2 t - 1)$ -set, hence $∣ C_{A} ∣ + ∣ C_{B} ∣ \leq 2 t - 1$ , so one of them, say $C_{A}$ , has size $\leq t - 1$ . But then the vertex of $A$ whose list is the $t$ -subset disjoint from $C_{A}$ (which exists, as $C_{A}$ omits at least $t$ colours) cannot be coloured from $C_{A}$ — contradiction. So no $L$ -colouring exists with lists of size $t$ , giving $ch (K_{k, k}) > t$ . Rubric: full credit for the $t$ -subset list construction, the disjointness of $C_{A}, C_{B}$ , and the omitted-subset contradiction.

Exercise 8 (hard, short-answer).

State the Combinatorial Nullstellensatz and use it to prove that a graph $G$ with an Alon-Tarsi orientation $D$ in which the numbers of even and odd Eulerian sub-digraphs differ is $ch^{'}$ -bounded by $max_{v} (d_{D}^{+} (v) + 1)$ . (You may prove the special case showing the graph polynomial has a nonzero coefficient.)

Hint

The graph polynomial is $f (x) = \prod_{ij \in E, i < j} (x_{i} - x_{j})$ . A nonzero coefficient on a monomial $\prod x_{v}^{t_{v}}$ with $t_{v} < ∣ L (v) ∣$ yields an $L$ -colouring by the Nullstellensatz.

Answer

Combinatorial Nullstellensatz (Alon 1999). Let $f \in F [x_{1}, \dots, x_{n}]$ have degree $\sum_{v} t_{v}$ , and suppose the coefficient of $\prod_{v} x_{v}^{t_{v}}$ in $f$ is nonzero. Then for any sets $S_{v}$ with $∣ S_{v} ∣ > t_{v}$ , there is a point $(s_{1}, \dots, s_{n}) \in \prod_{v} S_{v}$ with $f (s) \neq = 0$ . Apply it to the graph polynomial $f_{G} (x) = \prod_{{i, j} \in E, i < j} (x_{i} - x_{j})$ , whose degree is $∣ E ∣$ . A proper colouring is exactly an assignment making $f_{G} \neq = 0$ (each factor nonzero means adjacent vertices differ). Orient $G$ as $D$ ; expanding $f_{G}$ , the coefficient of $\prod_{v} x_{v}^{d_{D}^{+} (v)}$ equals (up to sign) the difference between the numbers of even and odd spanning Eulerian sub-digraphs of $D$ (Alon-Tarsi). If this difference is nonzero, then taking $S_{v} = L (v)$ with $∣ L (v) ∣ \geq d_{D}^{+} (v) + 1$ gives, by the Nullstellensatz, a point in $\prod L (v)$ with $f_{G} \neq = 0$ — an $L$ -colouring. Hence $ch (G) \leq max_{v} (d_{D}^{+} (v) + 1)$ ; the edge version applies the same argument to the line graph $L (G)$ . Rubric: full credit for the Nullstellensatz statement, the graph-polynomial reformulation of properness, and the Alon-Tarsi orientation coefficient yielding the choosability bound.

Advanced results Master

Theorem (König's edge-colouring theorem). Every bipartite graph $G$ satisfies $χ^{'} (G) = Δ (G)$ . (König ^{[Diestel 2017 §5.3]}; Diestel ^{[Diestel 2017 §5.3]}.) A bipartite graph of maximum degree $Δ$ embeds in a $Δ$ -regular bipartite graph, which by Hall's theorem 40.04.02 decomposes into $Δ$ perfect matchings; each matching is one colour class, so $Δ$ colours suffice and the degree bound is met. This is the bipartite face of Vizing: bipartite graphs are always class 1, the obstruction to class 1 being a parity phenomenon that odd structures alone create.

Theorem (Galvin 1995). For every bipartite (multi)graph $G$ , $ch^{'} (G) = χ^{'} (G) = Δ (G)$ . (Galvin ^{[Galvin 1995]}; Diestel ^{[Diestel 2017 §5.4]}.) The proof orients the line graph $L (G)$ so that it is kernel-perfect: properly $Δ$ -edge-colour $G$ by König's theorem, then orient each edge of $L (G)$ between two $G$ -edges of colours $i < j$ toward the lower colour at a shared vertex of one bipartition class and toward the higher at the other. Every induced subdigraph then has a kernel, obtained by a stable-matching (Gale-Shapley) argument on the colour preferences. A lemma of Bondy-Boppana-Siegel states that a digraph in which every induced subdigraph has a kernel is $f$ -choosable whenever $∣ L (v) ∣ > d^{+} (v)$ ; applied with the out-degrees bounded by $Δ - 1$ , it gives $ch^{'} (G) \leq Δ$ , and $ch^{'} \geq χ^{'} = Δ$ forces equality. Galvin's theorem is the first proved case of the list-edge-colouring conjecture.

Conjecture (list-edge-colouring conjecture). For every graph $G$ , $ch^{'} (G) = χ^{'} (G)$ . The edge version of choosability is conjectured to collapse to the chromatic index — edges, unlike vertices, are believed never to be hurt by adversarial lists. Galvin proved it for bipartite graphs; it is open in general, with asymptotic results (Kahn) showing $ch^{'} (G) = (1 + o (1)) χ^{'} (G)$ .

Theorem (Thomassen 1994). Every planar graph is $5$ -choosable. (Thomassen ^{[Thomassen 1994]}; Diestel ^{[Diestel 2017 §5.4]}.) The proof strengthens the statement to near-triangulations with a precoloured boundary edge and inducts on the number of vertices: in a $2$ -connected plane near-triangulation with outer cycle, two adjacent boundary vertices precoloured, every other boundary vertex given a list of size $\geq 3$ and every interior vertex a list of size $\geq 5$ , an $L$ -colouring exists. Removing a boundary vertex and distributing its constraints to its neighbours along the triangulated interior drives the induction. The bound $5$ is sharp: there are planar graphs that are not $4$ -choosable (Voigt 1993), even though every planar graph is $4$ -colourable.

Theorem (total colouring and the total-colouring conjecture). A total colouring colours vertices and edges together so that adjacent or incident objects differ; the total chromatic number $χ^{''} (G)$ satisfies $χ^{''} (G) \geq Δ + 1$ , and the conjecture of Vizing and Behzad is $χ^{''} (G) \leq Δ + 2$ . (See ^{[Diestel 2017 §5.3]}.) Total colouring fuses the vertex- and edge-colouring problems of this and the previous unit; the lower bound $Δ + 1$ is the maximum-degree vertex with its $Δ$ incident edges and itself, and the conjectured upper bound $Δ + 2$ is proved for planar graphs of large maximum degree and known asymptotically (Molloy-Reed: $χ^{''} \leq Δ + O (1)$ ).

Synthesis. These results are one circle of ideas seen at increasing depth, and putting these together edge colouring, list colouring, and total colouring become three readings of how a graph resists having its adjacencies separated into matchings or independent sets. The central insight is the surplus-colour and orientation principle: Vizing's $Δ + 1$ leaves every vertex a missing colour that the fan routes to the uncoloured edge, and this is exactly the out-degree slack that the Combinatorial Nullstellensatz and the kernel method exploit, so the foundational reason Galvin's bipartite list bound equals $Δ$ is the kernel-perfect orientation built from König's matching decomposition. The list chromatic number generalises the chromatic number of 40.04.06, and the gap $ch - χ$ that $K_{k, k}$ makes unbounded for vertices is dual to the gap $ch^{'} - χ^{'}$ that the list-edge-colouring conjecture says vanishes for edges — the structural asymmetry between vertices and edges that the line graph makes visible. The bridge from edges to the algebraic method is the graph polynomial: properness is the non-vanishing of $\prod_{i < j} (x_{i} - x_{j})$ , and the Alon-Tarsi orientation reads choosability off a single nonzero coefficient, the same Eulerian-sub-digraph count that controls Galvin's kernels. Total colouring is the closure that reunites the two colourings into one $Δ + 2$ question, and the bridge onward is the Tutte-polynomial and matroid framing of 40.04.06, where edge colourings of cubic graphs become nowhere-zero $4$ -flows.

Full proof set Master

Proposition 1 ( $χ^{'} (G) \geq Δ (G)$ , and colour classes are matchings). For every graph, $χ^{'} (G) \geq Δ (G)$ , and in any proper edge colouring each colour class is a matching.

Proof. Fix a proper edge colouring $c$ . If two edges $e, f$ share a vertex $w$ then $c (e) \neq = c (f)$ by definition, so each colour class — the set of edges of one colour — contains no two edges sharing a vertex, hence is a matching. At a vertex $v$ of maximum degree $Δ$ , its $Δ$ incident edges pairwise share $v$ , so they receive $Δ$ distinct colours; therefore at least $Δ$ colours appear, giving $χ^{'} (G) \geq Δ$ . $□$

Proposition 2 ( $χ^{'} (G) = χ (L (G))$ ). The chromatic index of $G$ equals the chromatic number of its line graph.

Proof. The line graph $L (G)$ has vertex set $E (G)$ with $e \sim f$ in $L (G)$ exactly when $e, f$ share an endpoint in $G$ . A map $c : E (G) \to {1, \dots, k}$ is a proper edge colouring of $G$ iff $c (e) \neq = c (f)$ whenever $e, f$ share an endpoint, iff $c$ is a proper vertex colouring of $L (G)$ . The least $k$ for which such a $c$ exists is $χ^{'} (G)$ on the left and $χ (L (G))$ on the right, so they coincide. $□$

Proposition 3 (Vizing's bound). Every simple graph satisfies $χ^{'} (G) \leq Δ (G) + 1$ .

Proof. Induct on $∣ E ∣$ , the empty graph being coloured. Remove an edge $e_{0} = v u_{0}$ , colour $G - e_{0}$ with $Δ + 1$ colours by induction, and extend. Each vertex misses a colour, the palette exceeding its degree. Form a maximal fan $u_{0}, u_{1}, \dots, u_{k}$ at $v$ where each $v u_{i}$ ( $i \geq 1$ ) carries a colour missing at $u_{i - 1}$ . If a colour $γ$ is missing at both $v$ and some $u_{i}$ , downshift the fan colours $c (v u_{j}) \leftarrow c (v u_{j + 1})$ for $j < i$ and set $c (v u_{i}) \leftarrow γ$ , then colour $v u_{0}$ with the colour freed at $u_{0}$ ; properness is preserved because each shifted colour was missing at the receiving vertex. Otherwise let $α$ miss $v$ and $β$ miss $u_{k}$ with $α \neq = β$ . Take the maximal $α β$ -alternating path (Kempe chain) from $v$ ; swapping $α, β$ on it makes $α$ missing at a fan vertex, reducing to the previous case for a subfan whose downshift frees a colour for $e_{0}$ . The Kempe chain cannot link $v$ to both $u_{j}$ (where $β$ enters the fan) and $u_{k}$ simultaneously, so one swap succeeds. Either way $e_{0}$ is coloured with $Δ + 1$ colours. $□$

Proposition 4 (König's edge-colouring theorem). Every bipartite graph $G$ has $χ^{'} (G) = Δ (G)$ .

Proof. It suffices to colour a $Δ$ -regular bipartite graph $H \supseteq G$ with $Δ$ colours and restrict. Build $H$ by adding vertices to equalise the two parts and edges to raise every degree to $Δ$ , keeping bipartiteness; this is possible since at each stage two vertices of degree $< Δ$ on opposite sides can be joined. A $Δ$ -regular bipartite graph satisfies Hall's condition: for $S$ in one part, the $Δ∣ S ∣$ edge-ends at $S$ land in $N (S)$ , which absorbs at most $Δ∣ N (S) ∣$ ends, so $∣ N (S) ∣ \geq ∣ S ∣$ ; Hall's theorem 40.04.02 yields a perfect matching $M_{1}$ . Then $H - M_{1}$ is $(Δ - 1)$ -regular bipartite; by induction on $Δ$ it decomposes into $Δ - 1$ perfect matchings, giving $Δ$ colour classes in all. So $χ^{'} (H) \leq Δ$ , hence $χ^{'} (G) \leq Δ$ , and Proposition 1 gives equality. $□$

Proposition 5 (choosability dominates the chromatic number, with strict gap possible). For every graph $ch (G) \geq χ (G)$ , and there exist bipartite graphs with $ch (G)$ arbitrarily larger than $χ (G) = 2$ .

Proof. Taking all lists equal to ${1, \dots, k}$ shows a $k$ -choosable graph is $k$ -colourable, so $ch (G) \geq χ (G)$ . For the gap, take $G = K_{k, k}$ with $k = (t 2 t - 1)$ and colours ${1, \dots, 2 t - 1}$ ; index each side's vertices by the $t$ -subsets and assign each vertex the list equal to its subset. If an $L$ -colouring existed, the colours used on the two sides would be disjoint (adjacent across the complete bipartite join), so one side uses $\leq t - 1$ colours and omits some $t$ -subset's worth of colours, leaving the vertex with that omitted list uncolourable — a contradiction. Hence $ch (K_{k, k}) > t$ while $χ (K_{k, k}) = 2$ . $□$

Proposition 6 (Galvin's theorem, kernel form). Every bipartite multigraph $G$ has $ch^{'} (G) = Δ (G)$ .

Proof. By König (Proposition 4), properly $Δ$ -edge-colour $G$ with colours $1, \dots, Δ$ . In the line graph $L = L (G)$ , orient the edge between two $G$ -edges $e, f$ sharing a vertex $w$ as follows: if $w$ lies in part $X$ , orient from the lower-coloured to the higher-coloured of $e, f$ ; if $w$ lies in part $Y$ , orient from higher to lower. Each vertex $e = x y$ of $L$ then has out-degree $d^{+} (e) \leq Δ - 1$ : at $x \in X$ the out-edges go to higher colours (at most $Δ - c (e)$ of them) and at $y \in Y$ to lower colours (at most $c (e) - 1$ ), summing to $\leq Δ - 1$ . This orientation is kernel-perfect: any induced subdigraph has a kernel, produced by the Gale-Shapley stable-matching procedure reading the colour order as preferences, so no induced subdigraph lacks an independent dominating set. By the Bondy-Boppana-Siegel lemma, a kernel-perfect digraph is $L$ -choosable whenever $∣ L (e) ∣ > d^{+} (e)$ ; with lists of size $Δ > Δ - 1 \geq d^{+} (e)$ this gives an $L$ -colouring, so $ch^{'} (G) \leq Δ$ . With $ch^{'} \geq χ^{'} = Δ$ , equality holds. $□$

Connections Master

Vertex colouring, Brooks' theorem, and the chromatic polynomial 40.04.06. This unit is the edge analogue of that one read through the line graph: $χ^{'} (G) = χ (L (G))$ and $ch^{'} (G) = ch (L (G))$ , so Vizing's $Δ + 1$ bound is the edge counterpart of the greedy $Δ + 1$ and Brooks' $Δ$ , and the class-1/class-2 split mirrors Brooks' clique/odd-cycle dichotomy. The chromatic polynomial of $L (G)$ counts proper edge colourings, and the choosability gap $ch - χ$ exhibited by $K_{k, k}$ is the list refinement of the chromatic number defined there.
Matchings, König's and Hall's theorems 40.04.02. König's edge-colouring theorem $χ^{'} (G) = Δ$ for bipartite graphs is exactly the decomposition of a $Δ$ -regular bipartite graph into $Δ$ perfect matchings, each colour class a matching by Proposition 1; Hall's marriage theorem supplies the matchings, and Galvin's list version routes the same matching decomposition through a kernel-perfect orientation. The min-max duality of König's matching theorem is the structural reason bipartite graphs never need the Vizing surplus colour.
Map colouring and planarity 40.04.08. Thomassen's theorem that planar graphs are $5$ -choosable is the list-colouring strengthening of the five-colour theorem, and edge colourings of cubic planar graphs are Tait colourings, equivalent to the four-colour theorem via nowhere-zero $4$ -flows; the co-produced map-colouring unit develops planarity and the four-colour theorem that this unit's choosability and edge-class results feed into. The sharpness of $5$ -choosability (planar graphs need not be $4$ -choosable) sits exactly against the $4$ -colourability proved there.
Multivariate polynomials and the Nullstellensatz 01.04.03 pending. The Combinatorial Nullstellensatz turns list colouring into a coefficient computation on the graph polynomial $\prod_{i < j} (x_{i} - x_{j})$ ; the Alon-Tarsi orientation reads choosability off the difference of even and odd Eulerian sub-digraph counts, an algebraic method whose engine is the polynomial-ring machinery developed there, and whose colouring application is the bridge between combinatorics and commutative algebra.

Historical & philosophical context Master

Edge colouring entered graph theory through map colouring: Peter Guthrie Tait's 1880 attempt on the four-colour theorem reduced it to $3$ -edge-colouring cubic planar bridgeless graphs, the "Tait colourings," tying the chromatic index to planarity decades before either was formalised. The decisive structural result is due to Vadim Vizing, whose 1964 paper On an estimate of the chromatic class of a p-graph (Diskret. Analiz 3) ^{[Vizing 1964]} proved that the chromatic index of a simple graph is $Δ$ or $Δ + 1$ , the fan-recolouring argument compressing the entire problem into a two-class dichotomy. The bipartite case is older: Dénes König's 1916 work on bipartite edge colouring established $χ^{'} = Δ$ for bipartite graphs as part of the matching theory of his 1936 textbook.

List colouring was introduced independently by Vizing in 1976 and by Paul Erdős, Arthur Rubin, and Herbert Taylor in 1979, who isolated choosability and gave the first $K_{k, k}$ -type separations between $ch$ and $χ$ . Carsten Thomassen's 1994 paper Every planar graph is 5-choosable (Journal of Combinatorial Theory B 62) ^{[Thomassen 1994]} gave a two-page induction settling the planar list-colouring number, and Margit Voigt's 1993 construction of a non- $4$ -choosable planar graph showed $5$ is sharp. The list-edge-colouring conjecture, that $ch^{'} = χ^{'}$ , was confirmed for bipartite multigraphs by Fred Galvin in 1995 (The list chromatic index of a bipartite multigraph, Journal of Combinatorial Theory B 63) ^{[Galvin 1995]} through a kernel-method argument resting on stable matchings. The algebraic method matured with Noga Alon and Michael Tarsi's 1992 orientation theorem and Alon's 1999 Combinatorial Nullstellensatz (Combinatorics, Probability and Computing 8) ^{[Alon 1999]}, which recast colouring existence as the non-vanishing of a polynomial coefficient.

Bibliography Master

@book{Diestel2017,
  author    = {Diestel, Reinhard},
  title     = {Graph Theory},
  edition   = {5th},
  series    = {Graduate Texts in Mathematics},
  volume    = {173},
  publisher = {Springer},
  year      = {2017}
}

@book{BondyMurty2008,
  author    = {Bondy, J. A. and Murty, U. S. R.},
  title     = {Graph Theory},
  series    = {Graduate Texts in Mathematics},
  volume    = {244},
  publisher = {Springer},
  year      = {2008}
}

@book{West2001,
  author    = {West, Douglas B.},
  title     = {Introduction to Graph Theory},
  edition   = {2nd},
  publisher = {Prentice Hall},
  year      = {2001}
}

@article{Vizing1964,
  author  = {Vizing, V. G.},
  title   = {On an estimate of the chromatic class of a p-graph},
  journal = {Diskret. Analiz},
  volume  = {3},
  year    = {1964},
  pages   = {25--30}
}

@article{Galvin1995,
  author  = {Galvin, Fred},
  title   = {The list chromatic index of a bipartite multigraph},
  journal = {Journal of Combinatorial Theory, Series B},
  volume  = {63},
  year    = {1995},
  pages   = {153--158}
}

@article{Thomassen1994,
  author  = {Thomassen, Carsten},
  title   = {Every planar graph is 5-choosable},
  journal = {Journal of Combinatorial Theory, Series B},
  volume  = {62},
  year    = {1994},
  pages   = {180--181}
}

@article{AlonTarsi1992,
  author  = {Alon, Noga and Tarsi, Michael},
  title   = {Colorings and orientations of graphs},
  journal = {Combinatorica},
  volume  = {12},
  year    = {1992},
  pages   = {125--134}
}

@article{Alon1999,
  author  = {Alon, Noga},
  title   = {Combinatorial Nullstellensatz},
  journal = {Combinatorics, Probability and Computing},
  volume  = {8},
  year    = {1999},
  pages   = {7--29}
}

@article{ErdosRubinTaylor1979,
  author  = {Erd\H{o}s, Paul and Rubin, Arthur L. and Taylor, Herbert},
  title   = {Choosability in graphs},
  journal = {Congressus Numerantium},
  volume  = {26},
  year    = {1979},
  pages   = {125--157}
}

Prerequisites

40.04.06

Tier anchors

beginner: Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) §5.3 (edge colouring) read for the timetable/scheduling picture; West 2001 *Introduction to Graph Theory* (2nd ed., Prentice Hall) §7.1 for the hand-drawn edge-colouring vocabulary and the round-robin tournament example; Wilson 1996 *Introduction to Graph Theory* Ch. 6 for the small worked edge-colourings
intermediate: Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) §5.3-§5.4 (the chromatic index, Vizing's theorem with the fan argument, König's edge-colouring theorem for bipartite graphs, list colouring and choosability); Bondy-Murty 2008 *Graph Theory* (Springer GTM 244) §17.1-§17.3 (edge colourings, Vizing, list edge colouring); West 2001 §7.1-§7.3 (chromatic index, Vizing, the line graph, list colouring)
master: Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) Ch. 5 §5.3-§5.4 (edge colouring, Vizing, list colouring, Galvin's theorem, the list-colouring conjecture) and §5.4 with Thomassen's 5-choosability of planar graphs; Bondy-Murty 2008 §17 (edge and list colouring); the original sources Vizing 1964, König 1916, Galvin 1995, Thomassen 1994, Alon-Tarsi 1992 and Alon 1999 (the Combinatorial Nullstellensatz)

References

Diestel 2017 — Graph Theory (5th edition) · Springer Graduate Texts in Mathematics 173, 2017, Ch. 5 (§5.3 edge colouring and Vizing's theorem with the fan-recolouring proof; §5.4 list colouring, choosability, Galvin's theorem for bipartite graphs, Thomassen's 5-choosability of planar graphs, the list-edge-colouring conjecture)
Bondy, Murty 2008 — Graph Theory · Springer Graduate Texts in Mathematics 244, 2008, §17.1-§17.3 (edge colourings, Vizing's theorem, line graphs, list edge colouring and the kernel method)
West 2001 — Introduction to Graph Theory · 2nd ed., Prentice Hall, 2001, §7.1-§7.3 (the chromatic index, Vizing's theorem, the line graph, König's edge-colouring theorem, list colouring and choosability)
Vizing 1964 — On an estimate of the chromatic class of a p-graph · Diskret. Analiz 3 (1964) 25-30 (Russian); the bound Delta <= chi' <= Delta + 1 for simple graphs, with the fan-recolouring argument
Galvin 1995 — The list chromatic index of a bipartite multigraph · Journal of Combinatorial Theory, Series B 63 (1995) 153-158; ch'(G) = chi'(G) = Delta for bipartite multigraphs via stable matchings / kernels
Thomassen 1994 — Every planar graph is 5-choosable · Journal of Combinatorial Theory, Series B 62 (1994) 180-181; the induction on a near-triangulation with two precoloured boundary vertices
Alon 1999 — Combinatorial Nullstellensatz · Combinatorics, Probability and Computing 8 (1999) 7-29; the polynomial method and its application to list colouring via the graph polynomial and Alon-Tarsi orientations

Estimated time

beginner: 18m
intermediate: 50m
master: 88m