Skip to Main content Skip to Navigation
Journal articles

On self-duality of branchwidth in graphs of bounded genus

Ignasi Sau Valls 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.
Document type :
Journal articles
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00736520
Contributor : Ignasi Sau <>
Submitted on : Friday, September 28, 2012 - 1:02:50 PM
Last modification on : Thursday, August 27, 2020 - 3:40:04 PM

Links full text

Identifiers

Collections

Citation

Ignasi Sau Valls, 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⟩

Share

Metrics

Record views

198