Back to Search Start Over

On Self-Duality of Branchwidth in Graphs of Bounded Genus

On Self-Duality of Branchwidth in Graphs of Bounded Genus

Authors :
Thilikos, Dimitrios M.
Monteil, Alain
Department of Mathematics [Athens]
National and Kapodistrian University of Athens (NKUA)
Source :
8th Cologne Twente Workshop on Graphs and Combinatorial Optimization (CTW), 8th Cologne Twente Workshop on Graphs and Combinatorial Optimization (CTW), 2009, Paris, France. pp.19-22
Publication Year :
2009
Publisher :
HAL CCSD, 2009.

Abstract

International audience; 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 more than a constant factor. Self-duality has been examined for several width-parameters, such as branchwidth in graphs in some surface. In this direction, we prove that $\\mathbf bw(G^*) \\leq 6\\times \\mathbf bw(G) +2g-4$ for any graph $G$ embedded in a surface of Euler genus $g$.

Details

Language :
English
Database :
OpenAIRE
Journal :
8th Cologne Twente Workshop on Graphs and Combinatorial Optimization (CTW), 8th Cologne Twente Workshop on Graphs and Combinatorial Optimization (CTW), 2009, Paris, France. pp.19-22
Accession number :
edsair.dedup.wf.001..93460af6290a4e565a63dc9caf711389