Galvin's Theorem for Bipartite Edge List Coloring

Edge Coloring with Individual Lists

In ordinary edge coloring, one chooses colors from a common palette and requires incident edges to receive different colors. List edge coloring makes the choice more restrictive: each edge has its own permitted list. Even if all lists have the same size, they need not contain the same colors. Galvin’s theorem gives a strong guarantee for bipartite graphs: lists as large as the maximum degree always suffice, including when parallel edges are present.

Throughout, a bipartite multigraph is finite and has no loops, but it may have parallel edges. Its vertex set is partitioned into \(X\) and \(Y\), and every edge joins a vertex of \(X\) to a vertex of \(Y\). Parallel edges are distinct edges, and they are counted separately in degrees. An edge coloring is proper if any two distinct edges incident with the same vertex have different colors.

We prove the theorem using a directed graph whose vertices represent edges of \(G\). The proof needs two ingredients: a proper edge coloring with \(\Delta(G)\) colors to order incident edges, and a list-coloring argument based on kernels. The ordering and orientation are chosen so that the directed outdegree of every edge-vertex is at most \(\Delta(G)-1\). Parallel edges require a directed graph that can have both arcs between the same pair of vertices.

Two Ingredients for the Proof

We first record why a proper edge coloring with \(\Delta(G)\) colors is available here. This is the bipartite edge-coloring result often called König’s line-coloring theorem. A short proof is included to make clear that parallel edges cause no difficulty.

Proof. First enlarge the two vertex parts with isolated vertices until they have the same size \(N\). Each side then has total degree at most \(ND\). Add parallel edges between vertices on opposite sides that still have degree less than \(D\), until all vertices have degree \(D\). This process is possible: the total degree deficit on each side is \(ND-|E|\), so whenever the deficit is positive, there is a deficient vertex on each side to join. The enlarged graph is \(D\)-regular.

Every \(D\)-regular bipartite multigraph with \(D\geq1\) has a matching covering its left side. Indeed, for any subset \(S\) of the left side, the \(D|S|\) edges incident with \(S\) all end in its neighborhood \(N(S)\), whose vertices are incident with at most \(D|N(S)|\) of these edges. Thus \(D|S|\leq D|N(S)|\), so \(|S|\leq|N(S)|\). Hall’s marriage theorem now gives a matching covering the left side. Since the two sides have equal size, this matching covers the right side as well.

For completeness, Hall’s condition implies such a matching by induction on the size of the left side. If a nonempty proper subset \(S\) has \(|N(S)|=|S|\), apply induction to the graph between \(S\) and \(N(S)\). For the remaining left vertices, Hall’s condition holds after deleting \(N(S)\): for any remaining subset \(T\), applying the original condition to \(S\cup T\) gives at least \(|S|+|T|\) neighbors, so at least \(|T|\) lie outside \(N(S)\). Induction matches the remaining vertices too. If no nonempty proper subset is tight, choose a left vertex \(x\) and a neighbor \(y\), and delete both. Any nonempty subset \(T\) of the remaining left side had at least \(|T|+1\) neighbors before deletion, so it still has at least \(|T|\). Induction applies, and adding \(xy\) completes the matching. The empty left side is the base case.

Removing a perfect matching from a \(D\)-regular bipartite multigraph leaves a \((D-1)\)-regular bipartite multigraph on the same vertices. Repeating this argument decomposes the edges into \(D\) matchings, which receive \(D\) different colors. Restrict this coloring to the original graph before the added edges and vertices were introduced. If \(D=0\), there are no edges and no coloring is needed. \(\square\)

The next lemma turns a kernel-perfect orientation with small outdegree into a list coloring. The outdegree \(d^+(v)\) is the number of distinct vertices to which there is an outgoing arc from \(v\); having two opposite arcs to one vertex still contributes one out-neighbor.

Proof. We use induction on the number of vertices. The graph with no vertices is colored by the empty assignment. Otherwise choose a color \(c\) appearing in at least one list, and let \(H\) be the subdigraph induced by vertices whose lists contain \(c\). Since \(D\) is kernel-perfect, \(H\) has a kernel \(K\). Give color \(c\) to every vertex in \(K\). This is proper on \(K\) because no two vertices of a kernel are adjacent.

Delete \(K\). For each remaining vertex \(v\), delete \(c\) from its list if \(c\in L(v)\). If \(c\in L(v)\), then \(v\in H\setminus K\), and the kernel property gives an outgoing arc from \(v\) to some vertex of \(K\). Thus at least one out-neighbor has been deleted, so the new outdegree is at most \(d^+(v)-1\), while the new list has size \(|L(v)|-1\geq d^+(v)\). If \(c\notin L(v)\), its list size is unchanged and its outdegree cannot increase. In either case its new list has size at least its new outdegree plus one. The induced subdigraph remaining after deletion is still kernel-perfect, by the definition. Induction colors it from the reduced lists. No remaining vertex uses \(c\), so adjoining the color \(c\) on \(K\) gives a proper list coloring of the whole graph. \(\square\)

Proof of Galvin’s Theorem

Proof. The case \(\Delta(G)=0\) has no edges, so the empty coloring works. Suppose \(\Delta=\Delta(G)\geq1\). By the bipartite edge-coloring lemma, fix a proper edge coloring \(\varphi\) of \(G\) using colors \(1,\dots,\Delta\); unused colors are allowed. Form a directed graph \(D\) whose vertices are the edges of \(G\). Two distinct vertices of \(D\) are adjacent whenever their corresponding edges share an endpoint in \(G\).

For two such edge-vertices \(e,f\), insert an arc \(e\to f\) from their common endpoint according to the following rules: at an endpoint in \(X\), insert \(e\to f\) if \(\varphi(e)<\varphi(f)\); at an endpoint in \(Y\), insert \(e\to f\) if \(\varphi(e)>\varphi(f)\). When \(e,f\) are parallel, they share both endpoints. Since their colors are distinct, the \(X\)-rule and \(Y\)-rule give opposite arcs. Both arcs are inserted. This is intentional: the directed graph may have opposite arcs between a pair, and kernels and out-neighbors are understood as defined above.

Fix an edge \(e=xy\), where \(x\in X\), \(y\in Y\), and let \(i=\varphi(e)\). At \(x\), the other incident edges have distinct colors, and at most \(\Delta-i\) have color greater than \(i\). At \(y\), the other incident edges have distinct colors, and at most \(i-1\) have color less than \(i\). The out-neighbors of \(e\) are among the edges counted by these two bounds, so even if a parallel edge is counted at both endpoints, the number of distinct out-neighbors is at most their sum: \[ d^+(e)\leq(\Delta-i)+(i-1)=\Delta-1. \] In particular, every list \(L(e)\) of size at least \(\Delta\) satisfies \(|L(e)|\geq d^+(e)+1\).

It remains to verify that \(D\) is kernel-perfect. Take any induced subdigraph, corresponding to a subset \(F\subseteq E(G)\), and consider the bipartite multigraph with edge set \(F\) and the same vertex parts. At each vertex of \(X\), let its incident edges in \(F\) be ordered from highest \(\varphi\)-color to lowest; at each vertex of \(Y\), order them from lowest \(\varphi\)-color to highest. Run the following proposing procedure: vertices in \(X\) propose to incident edge-copies in this preference order; a vertex in \(Y\) holds its most preferred proposal so far and rejects any less preferred proposal, rejecting a previously held proposal if it receives a better one. A vertex in \(X\) that is rejected continues to its next edge-copy. Each edge-copy is proposed to at most once, so the procedure terminates.

The proposals held at termination pair each matched vertex of \(X\) with one edge-copy and pair that copy with its endpoint in \(Y\); these pairs form a matching \(M\) of edges of \(F\). For every edge \(e\in F\setminus M\), at least one endpoint is matched to an edge it prefers to \(e\). To see this, if its \(X\)-endpoint prefers \(e\) to its final partner (or has no partner), it must have proposed to \(e\); the \(Y\)-endpoint then rejected it or later replaced it with an edge it prefers. Otherwise the \(X\)-endpoint is already matched to an edge it prefers to \(e\). By the ordering rules, an edge \(e\) has an outgoing arc to any incident edge preferred to it at that endpoint: at \(X\), preference is toward higher \(\varphi\)-color, and at \(Y\), toward lower \(\varphi\)-color. Thus every edge-vertex outside \(M\) has an outgoing arc to a vertex in \(M\). The matching \(M\) is independent in the underlying edge-adjacency graph, so it is a kernel. This works for every \(F\), proving that \(D\) is kernel-perfect.

The kernel list-coloring lemma now gives a proper coloring of the edge-vertices from their lists. Adjacency in the underlying graph of \(D\) means precisely that the corresponding edges share an endpoint in \(G\); therefore this coloring is a proper list edge coloring of \(G\). \(\square\)

Worked Examples

Why the Parallel-Edge Detail Matters

A common mistake is to try to define just one direction between two vertices representing parallel edges, then claim that both endpoint rules agree. They do not. If \(\varphi(e)<\varphi(f)\), the rule at the \(X\)-endpoint inserts \(e\to f\), while the rule at the \(Y\)-endpoint inserts \(f\to e\). The correct construction inserts both arcs. The outdegree estimate still works because it bounds the number of distinct out-neighbors by the sum of the two endpoint counts. A shared neighbor counted twice in that sum only makes the upper bound looser; it does not invalidate it.

The proof has two distinct safeguards. Properness of the auxiliary edge coloring ensures that incident edges have different \(\varphi\)-colors, which is needed for the endpoint counts. Kernel-perfectness is established on every subset of edges, not just on the full graph; this is what lets the list-coloring lemma apply after vertices and colors are successively removed. Replacing either condition with a statement about only the original full graph would leave a gap.

Galvin’s theorem is stronger than ordinary edge-colorability: lists may vary edge by edge, and their colors need not come from a single common palette. Its conclusion matches the familiar degree threshold for bipartite edge coloring, but its proof uses the lists’ sizes together with the orientation’s outdegree bound. The theorem does not assert the same conclusion for arbitrary non-bipartite multigraphs; bipartiteness is essential to the edge-coloring and matching structure used here.