License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2022.1
URN: urn:nbn:de:0030-drops-161618
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16161/
Go to the corresponding LIPIcs Volume Portal

Bar-Noy, Amotz ; Böhnlein, Toni ; Peleg, David ; Rawitz, Dror

On Realizing a Single Degree Sequence by a Bipartite Graph (Invited Paper)

pdf-format:
LIPIcs-SWAT-2022-1.pdf (0.9 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{barnoy_et_al:LIPIcs.SWAT.2022.1,
  author =	{Bar-Noy, Amotz and B\"{o}hnlein, Toni and Peleg, David and Rawitz, Dror},
  title =	{{On Realizing a Single Degree Sequence by a Bipartite Graph}},
  booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
  pages =	{1:1--1:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-236-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{227},
  editor =	{Czumaj, Artur and Xin, Qin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16161},
  URN =		{urn:nbn:de:0030-drops-161618},
  doi =		{10.4230/LIPIcs.SWAT.2022.1},
  annote =	{Keywords: Degree Sequences, Graph Realization, Bipartite Graphs, Graphic Sequences, Bigraphic Sequences, Multigraph Realization}
}

Keywords: Degree Sequences, Graph Realization, Bipartite Graphs, Graphic Sequences, Bigraphic Sequences, Multigraph Realization
Collection: 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)
Issue Date: 2022
Date of publication: 22.06.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI