On self-duality of branchwidth in graphs of bounded genus - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue Discrete Applied Mathematics Année : 2011

On self-duality of branchwidth in graphs of bounded genus

Résumé

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. Self-duality has been examined for several width parameters, such as branchwidth, pathwidth, and treewidth. In this paper, we give a direct proof of the self-duality of branchwidth in graphs embedded in some surface. In this direction, we prove that bw(G*) < 6bw(G)+2g-3 for any graph G embedded in a surface of Euler genus g.

Dates et versions

lirmm-00736520 , version 1 (28-09-2012)

Identifiants

Citer

Ignasi Sau, Dimitrios M. Thilikos. On self-duality of branchwidth in graphs of bounded genus. Discrete Applied Mathematics, 2011, 159 (17), pp.2184-2186. ⟨10.1016/j.dam.2011.06.028⟩. ⟨lirmm-00736520⟩
100 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More