Branchwidth is (1,g)-self-dual

arXiv (Cornell University)

Abstract

A graph parameter is self-dual in some class of graphs embeddable in some surface if its value does not change in the dual graph by more than a constant factor. We prove that the branchwidth of connected hypergraphs without bridges and loops that are embeddable in some surface of Euler genus at most g is an (1,g)-self-dual parameter. This is the first proof that branchwidth is an additively self-dual width parameter.

Authors 5

1. Georgios Kontogeorgiou

   University of Warwick

   Affiliation as printed

   Mathematics Institute , University of Warwick , CV4 7AL , UK

2. Alexandros Leivaditis Aachen Mathematical Institute

   Leiden University

   Affiliation as printed

   Mathematical Institute , Universiteit Leiden , Netherlands

3. Kostas I. Psaromiligkos

   University of Chicago

   Affiliation as printed

   Department of Mathematics , University of Chicago , Chicago , IL , USA

4. Giannos Stamoulis

   Centre National de la Recherche Scientifique · Université de Montpellier · Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier

   Affiliation as printed

   LIRMM , Univ Montpellier , CNRS , Montpellier , France and

5. Dimitris Zoros

   National and Kapodistrian University of Athens

   Affiliation as printed

   Department of Mathematics , National and Kapodistrian University of Athens , Athens , Greece

   Inter-university Postgraduate Programme "Algorithms, Logic, and Discrete Mathematics" (ALMA). Supported by the French-German Collaboration ANR/DFG Project UTMA