Search

We prove an extension of Galvin's theorem, namely that any graph is L-edge-choosable if |L(e)|≥χ′(G) and the edge-lists of no odd cycle contain a common colour. [ABSTRACT FROM AUTHOR]

We describe a flow model related to ordinary network flows the same way as stable matchings are related to maximum matchings in bipartite graphs. We prove that there always exists a stable flow and generalize the lattice structure of stable marriages to stable flows. Our main tool is a straightforward reduction of the stable flow problem to stable allocations. For the sake of completeness, we prove the results we need on stable allocations as an application of Tarski's fixed point theorem. [ABSTRACT FROM AUTHOR]

Abstract: Galvin solved the Dinitz conjecture by proving that bipartite graphs are Δ-edge-choosable. We employ Galvin''s method to show some further list edge-colouring properties of bipartite graphs. In particular, there exist balanced list edge-colourings for bipartite graphs. In the light of our result, it is a natural question whether a certain generalization of the well-known list colouring conjecture is true. [Copyright &y& Elsevier]

Abstract: As a generalisation of the stable matching problem Baïou and Balinski (2002)  defined the stable allocation problem for bipartite graphs, where both the edges and the vertices may have capacities. They constructed a so-called inductive algorithm, that always finds a stable allocation in strongly polynomial time. Here, we generalise their algorithm for non-bipartite graphs with integral capacities. We show that the algorithm does not remain polynomial, although we also present a scaling technique that makes the algorithm weakly polynomial. [Copyright &y& Elsevier]

We characterize the bipartite stable b-matching polytope in terms of linear constraints. The stable b-matching polytope is the convex hull of the characteristic vectors of stable b-matchings, that is, of stable assignments of a two-sided multiple partner matching model. Our proof uses a generalization by Baı¨ou and Balinski of the comparability theorem of Roth and Sotomayor and follows a similar line as the proof of Rothblum's characterization of the stable matching polytope. [Copyright &y& Elsevier]

We describe a fixed-point based approach to the theory of bipartite stable matchings. By this, we provide a common framework that links together seemingly distant results, like the stable marriage theorem of Gale and Shapley, the Mendelsohn-Dulmage theorem, the Kundu-Lawler theorem, Tarski's fixed-point theorem, the Cantor-Bernstein theorem, Pym's linking theorem, or the monochromatic path theorem of Sands et al. In this framework, we formulate a matroid-generalization of the stable marriage theorem and study the lattice structure of generalized stable matchings. Based on the theory of lattice polyhedra and blocking polyhedra, we extend results of Vande Vate and Rothblum on the bipartite stable matching polytope. [ABSTRACT FROM AUTHOR]