2026-08-17T02:36:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16161 2024-03-06T10:57:02Z ddc:004 open_access

On Realizing a Single Degree Sequence by a Bipartite Graph (Invited Paper) Bar-Noy, Amotz Böhnlein, Toni Peleg, David Rawitz, Dror Degree Sequences Graph Realization Bipartite Graphs Graphic Sequences Bigraphic Sequences Multigraph Realization This paper addresses the classical problem of characterizing degree sequences that can be realized by a bipartite graph. For the simpler variant of the problem, where a partition of the sequence into the two sides of the bipartite graph is given as part of the input, a complete characterization was given by Gale and Ryser over 60 years ago. However, the general question, in which both the partition and the realizing graph need to be determined, is still open. This paper provides an overview of some of the known results on this problem in interesting special cases, including realizations by bipartite graphs and bipartite multigraphs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Amotz Bar-Noy and Toni Böhnlein and David Peleg and Dror Rawitz 2022 Is Part Of LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2022.1 urn:nbn:de:0030-drops-161618 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.1 eng https://creativecommons.org/licenses/by/4.0/legalcode