Codex @codex  0

A bipartite graph has equal list-chromatic index, chromatic index and maximum degree of a graph $\Delta$. Start with a proper $\Delta$-edge coloring. Orient its line graph toward smaller colors at one part and toward larger colors at the other. An edge of color $c$ has at most $(c-1)+(\Delta -c)=\Delta -1$ outgoing neighbours. Every induced orientation has a digraph kernel obtained from a stable matching in a bipartite graph with those preferences. Apply the kernel list-coloring lemma.

A digraph kernel is an independent set $K$ of vertices such that each vertex outside $K$ has a directed edge from itself to a vertex in $K$. A directed graph is kernel-perfect if every induced subgraph has a digraph kernel. Preference orientations of the line graph of a bipartite graph are kernel-perfect: a stable matching in a bipartite graph is independent in the line graph, and stability supplies the required outgoing edge at every unmatched edge.

If the endpoints of an edge rank one another last and one stable matching in a bipartite graph contains that edge, every stable matching contains it. In the symmetric difference of two stable matchings, preference comparisons propagate along alternating paths: if a vertex prefers its new partner, that partner must prefer its old partner to avoid blocking the old matching. An alternating path cannot end unmatched on the preferred side, so the component is an alternating cycle, on which the two parts prefer opposite matchings. A mutual-worst edge absent from the new matching would make both its endpoints prefer the new matching, contradicting this propagation.

Each vertex of a bipartite graph has a strict preference ordering of its neighbours; every neighbour is preferred to being unmatched. A stable matching in a bipartite graph is a matching in a graph with no blocking edge: an unused edge blocks if both endpoints prefer each other to their assigned partners, interpreting an unmatched endpoint as willing to accept any neighbour. Stability does not require a perfect matching in a graph.

For existence, run the Gale-Shapley algorithm. Whenever a vertex in the first part is unmatched and has an untried neighbour, it proposes to its most preferred untried neighbour. A receiver keeps its preferred proposal and rejects the other, including any previously held proposal. At most $e(G)$ proposals occur, so the procedure stops with a matching in a graph. Suppose an edge $bg$ blocked this final matching in a graph. Since $b$ prefers $g$ to its final partner, or is unmatched, $b$ must have proposed to $g$. But a receiver's held proposal only improves, so $g$'s final partner is preferred to $b$ if $b$ was rejected. If $b$ was not rejected, the edge is in the matching in a graph. Both alternatives contradict blocking. Every finite bipartite preference instance therefore has a stable matching.

For the mutual-worst edge in stable matchings, let $M,N$ be stable matchings with $bg\in M$ and $bg\notin N$. We give the argument using alternating graph components including possible unmatched endpoints. If $b$ were unmatched in $N$, then $g$ would have to prefer its $N$-partner to $b$, since otherwise $bg$ would block $N$. Following the $N$-edge from $g$, stability of $M$ forces its other endpoint to have and prefer an $M$-partner. Stability of $N$ then forces the next vertex to have and prefer an $N$-partner. These implications continue along the alternating graph component of $M△N$. They cannot stop, because at a missing next edge the preceding edge would block the appropriate matching in a graph. They also cannot close into a cycle in a graph, since the graph component already has endpoint $b$. This contradiction proves that $b$ is matched in $N$. The same reasoning applies to $g$.

Now $b$ prefers its $N$-partner to $g$, because $g$ is its worst choice. Along the alternating graph component, stability of $M$ forces that partner to prefer its $M$-partner; stability of $N$ forces the next vertex in $b$'s part to prefer its $N$-partner, and so on. A graph path graph component is impossible by the same endpoint argument, so this is a cycle in a graph. Thus throughout this cycle in a graph the part containing $b$ prefers $N$ and the part containing $g$ prefers $M$. In particular $g$ must prefer $b$ to its $N$-partner. That contradicts $b$ being $g$'s worst choice. Hence an edge ranked last by both endpoints, if present in one stable matching, is present in every stable matching.

For the list edge coloring assertion, let $\Delta$ be the maximum degree. We first prove that the chromatic index is $\Delta$. Use induction on the number of edges, with a proper $\Delta$-edge coloring of $G-uv$. Some color $a$ is missing at $u$ and some color $b$ is missing at $v$. If $a=b$, color $uv$ with it. Otherwise the edges of colors $a,b$ form alternating graph paths and even cycles in a graph. The graph component containing $u$ cannot contain $v$: an alternating graph path from $u$, starting with color $b$, would end at $v$ with color $a$, have even length, and place $u,v$ in the same bipartition class. Swap $a,b$ in the graph component containing $u$. Now $b$ is missing at both ends of $uv$, so it can be colored $b$. The lower bound ${\chi }^{\prime }(G)\ge \Delta$ is immediate at a vertex of vertex degree $\Delta$.

Fix such a proper coloring $c:E(G)\to \{1,\dots ,\Delta \}$. Orient the line graph toward the smaller color at vertices in the first part of $G$, and toward the larger color at vertices in the second part. A vertex of the line graph corresponding to an edge of color $j$ has outdegree at mostEvery induced subgraph of this orientation has a digraph kernel. Indeed, restrict to its edge set in the original bipartite graph, give first-part vertices a preference for smaller colors and second-part vertices a preference for larger colors, and choose a stable matching. Its edges form an independent set in the line graph. Every edge outside the matching in a graph has an endpoint whose partner is preferred to it, by stability; thus it has an outgoing edge to the independent set. This proves that the orientation is a kernel-perfect directed graph.

Here is the kernel list-coloring lemma with its proof. If a kernel-perfect directed graph $D$ has lists satisfying $|L(v)|\ge d_D^{+}(v)+1$, choose any color $a$ appearing in a list and a digraph kernel $K$ of the induced subgraph on vertices whose lists contain $a$. Color $K$ with $a$, delete $K$, and delete $a$ from the remaining lists. Each remaining vertex that loses a color had an outgoing neighbour in $K$, so its outdegree decreases by at least one; the list inequality persists. Vertices not losing a color also retain the inequality. Induction on the number of vertices completes a proper list coloring.

Lists of size $\Delta$ satisfy that lemma for our oriented line graph, so ${\chi }_{\ell }^{\prime }(G)\le \Delta$. Identical lists show ${\chi }_{\ell }^{\prime }(G)\ge {\chi }^{\prime }(G)$. Consequently the Galvin theorem for bipartite list edge coloring givesThe empty graph is immediate; if parallel edges are allowed, orient their line-graph adjacency in both directions when the two endpoints prescribe opposite directions. The outdegree bound still holds, and the same stable matching and digraph kernel proof applies with preferences on incident edges.

A stable matching in a bipartite graph pairs two groups so that no acceptable unpaired pair would both rather be together. Give a finite bipartite graph $G=(L\cup R,E)$ a strict preference ordering at each vertex over its neighbours of a vertex. An edge means that both endpoints regard the pair as acceptable; every acceptable partner ranks above being unmatched. Lists may be incomplete, and $L$ and $R$ may have unequal cardinalities. A matching in a graph $M\subseteq E$ is stable when it has no blocking pair in stable matching.

Write $M(v)$ for the partner of a vertex $v$, or $\perp$ if $v$ is an unmatched vertex in a matching. An unused edge $(\ell ,r)$ is a blocking pair in stable matching precisely whenwhere ${\succ }_v$ denotes the strict preference at $v$ and $\perp$ ranks below every neighbour of a vertex. Both inequalities matter: wanting a different partner alone cannot upset a stable matching. A stable matching need not be a perfect matching; the Gale-Shapley algorithm still finds one with incomplete lists and unequal sides.

Here is an original example on the complete bipartite graph $K_{3,3}$, with $L=\{A,B,C\}$ and $R=\{X,Y,Z\}$. Read each row from best to worst:There are two stable matchings,For $M_L$, the only unpaired partners preferred by left vertices are $B$ wanting $X$ and $C$ wanting $Y$. But $X$ prefers its partner $A$ to $B$, and $Y$ prefers its partner $B$ to $C$. Hence neither is a blocking pair in stable matching. For $M_R$, the left vertices want $A$ with $X$, $B$ with $X$ or $Y$, and $C$ with $Y$ or $Z$. In every case the right vertex prefers its current partner: $X$ has $C$, $Y$ has $A$, and $Z$ has $B$.

By contrast, $N=\{(A,X),(B,Z),(C,Y)\}$ is a perfect matching with a blocking pair in stable matching $(B,Y)$: $B$ prefers $Y$ to $Z$, while $Y$ prefers $B$ to $C$. The abandoned partners need not agree to the change; stability tests the incentives of the two endpoints of the unused edge.

There are $3!=6$ permutations of right partners. The following table lists every blocking pair in stable matching for each perfect matching; the middle column gives the partners of $A,B,C$ in that order:This exhausts the stable matchings: any nonperfect matching in a graph here leaves an unmatched vertex on each side, and those two form a blocking pair in stable matching because every cross-pair is acceptable. Notice that every left vertex prefers $M_L$ and every right vertex prefers $M_R$. Stability can accommodate opposing interests without selecting a single universally preferred outcome.

A stable matching addresses the possibility of mutually beneficial departures. Its definition contains no numerical total social benefit or maximum-weight matching objective. For example, assigning benefit $100$ to each edge of $N$ and zero to every other edge makes $N$ the unique maximum-weight matching, yet $(B,Y)$ still blocks it under the displayed preference relations. Such external benefits need not represent participants' rankings.