Skip to Main content Skip to Navigation
Journal articles

On self-duality of branchwidth in graphs of bounded genus

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 metadata
Contributor : Ignasi Sau <>
Submitted on : Friday, September 28, 2012 - 1:02:50 PM
Last modification on : Thursday, November 26, 2020 - 4:00:02 PM

Links full text




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⟩



Record views