Kernel Orientations in Galvin's Theorem

From Edge Coloring to an Orientation

Galvin’s theorem says that the edge-list coloring bound for a bipartite graph is its maximum degree. The key idea is to turn the edge-coloring problem into a vertex-list coloring problem on the line graph. A carefully chosen orientation of that line graph has two useful properties: every induced subdigraph has a kernel, and each vertex has outdegree at most one less than the maximum degree. A kernel lemma then converts those properties into a list coloring.

All graphs in this tutorial are finite and simple. A proper edge coloring assigns colors to edges so that edges sharing an endpoint receive different colors. For a graph \(G\), its line graph \(L(G)\) has one vertex for each edge of \(G\), with two vertices adjacent exactly when the corresponding edges share an endpoint. A digraph is an orientation of a graph when each edge is given exactly one of its two possible directions.

The condition that arcs point toward the kernel is important. In a line graph, an independent set is a set of pairwise nonincident edges in the original graph, hence a matching. Thus a kernel in an oriented line graph is a matching such that every other edge has an arc pointing to one of its edges.

Constructing the Orientation

Let \(G\) be bipartite with parts \(X,Y\), and let \(\Delta=\Delta(G)\). When \(G\) has at least one edge, the König line-coloring theorem gives a proper edge coloring with colors \(1,\ldots,\Delta\). This standard edge-coloring result is used here without reproving it. For each edge \(e\), write \(c(e)\) for its color.

Orient each adjacency in \(L(G)\) according to the endpoint where the two edges meet. At a common endpoint in \(X\), direct the arc from the lower-colored edge to the higher-colored edge. At a common endpoint in \(Y\), direct it from the higher-colored edge to the lower-colored edge. Properness ensures that two edges sharing an endpoint have distinct colors, so exactly one of these directions is assigned.

It is useful to interpret the orientation as preferences. At a vertex of \(X\), higher colors are preferred; at a vertex of \(Y\), lower colors are preferred. In both cases, an arc \(e\to f\) means that at their common endpoint, \(f\) is preferred to \(e\). This direction convention makes a stable matching into a kernel.

Why Every Induced Subdigraph Has a Kernel

Take any subset \(F\subseteq E(G)\). The induced subdigraph on the corresponding vertices of \(L(G)\) is the orientation formed by just those edges. To find its kernel, regard \((V(G),F)\) as a bipartite graph and give each endpoint the preferences defined by the edge colors. The preferences are strict, because incident edges have distinct colors.

We use the deferred-acceptance procedure: vertices in \(X\) propose to incident edges in order of preference, and vertices in \(Y\) hold at most one proposal, keeping their most-preferred proposal so far. If a vertex in \(Y\) replaces a held proposal, the rejected vertex in \(X\) may propose to its next choice. A vertex never proposes to the same edge twice.

Proof. Run deferred acceptance on the finite set \(F\). Each proposal uses a previously untried incident edge, so there are at most \(|F|\) proposals and the procedure terminates. The held proposals at termination form a matching \(M\): each vertex of \(Y\) holds at most one, and each vertex of \(X\) has at most one proposal held.

We verify stability. Call an edge \(e=xy\in F\) a blocking edge if both endpoints prefer \(e\) to their held edge, where an unmatched endpoint prefers any incident edge to being unmatched. Suppose \(x\) prefers \(e\) to its final held edge, or \(x\) is unmatched. Then \(x\) proposed to \(e\): proposals are made in preference order, and the procedure cannot stop at a less-preferred final choice without having tried \(e\). Vertex \(y\) must then either have rejected \(x\) immediately or later replaced \(x\) with a more-preferred proposal. Since \(y\) only replaces a held proposal when it receives a better one, its final held edge is preferred to \(e\). Thus \(e\) cannot block. This proves that \(M\) is stable.

Since \(M\) is a matching, it is an independent set in the line graph. For any \(e=xy\in F\setminus M\), stability says that \(x\) and \(y\) do not both prefer \(e\) to their held edges. An unmatched endpoint would prefer \(e\), so at least one endpoint must be matched and prefer its held edge \(f\) to \(e\). The orientation rule directs \(e\to f\), because arcs point from the less-preferred edge to the more-preferred one at that endpoint. Therefore every vertex outside \(M\) has an arc to \(M\), and \(M\) is a kernel. The argument applies to every \(F\), including \(F=\varnothing\), whose empty digraph has the empty kernel. \(\square\)

The Outdegree Bound and the Kernel Lemma

Fix an edge \(e\) of color \(i\), with endpoints \(x\in X\) and \(y\in Y\). At \(x\), an outgoing arc from \(e\) goes to an incident edge of color greater than \(i\). There are at most \(\Delta-i\) such colors among \(1,\ldots,\Delta\), and properness means at most one incident edge of each color. At \(y\), an outgoing arc goes to an incident edge of color less than \(i\), so there are at most \(i-1\) such edges. The two groups account for all neighbors of \(e\) in the line graph. Hence \[ d^+(e)\le(\Delta-i)+(i-1)=\Delta-1. \] This bound also holds when an endpoint has degree less than \(\Delta\), since that can only reduce the number of outgoing arcs.

Proof. We use induction on \(|V(D)|\). If \(V(D)=\varnothing\), the empty coloring works. Otherwise choose a vertex \(v\) and a color \(c\in L(v)\). Let \(S=\{u\in V(D):c\in L(u)\}\), which is nonempty since \(v\in S\). Kernel-perfectness gives a kernel \(K\) in the subdigraph induced by \(S\). The kernel is nonempty: if it were empty, a vertex of the nonempty set \(S\) would have to send an arc to a vertex of the empty set, which is impossible.

Color every vertex of \(K\) with \(c\), and delete \(K\). This assigns one color to an independent set. For each remaining \(u\in S\setminus K\), remove \(c\) from its list. The kernel property gives at least one arc from \(u\) to \(K\), so deleting \(K\) reduces its outdegree by at least one. Its new list size is at least \(d^+(u)\), which is at least \(d^+_{D-K}(u)+1\). For \(u\notin S\), its list is unchanged, and its outdegree cannot increase, so its list still has size at least \(d^+_{D-K}(u)+1\).

The induced digraph \(D-K\) is kernel-perfect: every one of its induced subdigraphs is also an induced subdigraph of \(D\). The induction hypothesis therefore colors \(D-K\) from the adjusted lists. No remaining vertex can receive \(c\) if it was adjacent to \(K\): a vertex in \(S\setminus K\) had \(c\) removed, and a vertex outside \(S\) never had \(c\). Together with the color \(c\) on the independent set \(K\), this is a proper list coloring of \(D\). \(\square\)

Galvin’s Theorem

Proof. If \(G\) has no edges, the empty edge coloring satisfies the conclusion. Otherwise, use the König line-coloring theorem to choose a proper edge coloring with colors \(1,\ldots,\Delta\), and orient \(L(G)\) by the rule above. The stability lemma proves that this orientation is kernel-perfect, and the outdegree calculation gives \(d^+(e)\le\Delta-1\) for every vertex \(e\) of the line graph. Therefore \(|L(e)|\ge\Delta\ge d^+(e)+1\). The kernel lemma gives a proper vertex-list coloring of \(L(G)\). By the definition of the line graph, this is exactly a proper edge-list coloring of \(G\). \(\square\)

Why the Orientation Matters

The line graph alone does not record which endpoint of an edge should govern a preference. The bipartition supplies that distinction: high colors are preferred on one side and low colors on the other. This opposite ordering is what lets the outdegree contributions fit together as \((\Delta-i)+(i-1)=\Delta-1\). The stable-matching argument then supplies kernels not merely in the whole orientation but in every induced subdigraph, exactly the hypothesis needed by the kernel lemma.

Common pitfall: reversing the kernel condition. A set is not a kernel merely because every outside vertex is adjacent to it. The required direction is an arc from each outside vertex to the kernel. In the first example, \(\{ab\}\) is not a kernel of the full oriented line graph: although it is independent, the vertex \(cd\) has no arc to \(ab\), since \(cd\) and \(ab\) are not adjacent. By contrast, the kernel \(\{e_{12},e_{21}\}\) in the second example works because the outside vertices have the specific arcs \(e_{11}\to e_{12}\) and \(e_{22}\to e_{21}\). Checking adjacency without checking arrow direction would not establish the kernel property.