On Galvin's Theorem and Stable Matchings

Abstract

In this thesis, we will discuss list edge coloring and its relation to stable matchings. In particular, we will present three proofs of Galvin's famous theorem that bipartite graphs satisfy the list edge coloring conjecture. Galvin presented two of these proofs in his original paper, one by induction and another using stable matchings and the Gale-Shapley Theorem about stable matchings in bipartite graphs. The third proof we present is a corollary of a more general result proven by Borodin, Kostochka, and Woodall. We will study the techniques of these proofs to find a characterization of graphs that have stable matchings with respect to their preference lists, and two alternative proofs of the Gale-Shapley Theorem. We will also consider some new generalizations of stable matchings.