On self-duality of branchwidth in graphs of bounded genus

Ignasi Sau 1 Dimitrios M. Thilikos 2
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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. 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.
Type de document :
Article dans une revue
Discrete Applied Mathematics, Elsevier, 2011, 159 (17), pp.2184-2186. 〈10.1016/j.dam.2011.06.028〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00736520
Contributeur : Ignasi Sau <>
Soumis le : vendredi 28 septembre 2012 - 13:02:50
Dernière modification le : vendredi 7 septembre 2018 - 14:04:02

Lien texte intégral

Identifiants

Collections

Citation

Ignasi Sau, Dimitrios M. Thilikos. On self-duality of branchwidth in graphs of bounded genus. Discrete Applied Mathematics, Elsevier, 2011, 159 (17), pp.2184-2186. 〈10.1016/j.dam.2011.06.028〉. 〈lirmm-00736520〉

Partager

Métriques

Consultations de la notice

122