On Self-Duality of Branchwidth in Graphs of Bounded Genus

1 Dimitrios M. Thilikos
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
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 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$.
Type de document :
Communication dans un congrès
8th Cologne Twente Workshop on Graphs and Combinatorial Optimization (CTW), 2009, Paris, France. pp.19-22, 2009


https://hal.inria.fr/hal-00795413
Contributeur : Alain Monteil <>
Soumis le : jeudi 28 février 2013 - 10:54:46
Dernière modification le : jeudi 28 février 2013 - 10:54:46

Identifiants

  • HAL Id : hal-00795413, version 1

Collections

Citation

, Dimitrios M. Thilikos. On Self-Duality of Branchwidth in Graphs of Bounded Genus. 8th Cologne Twente Workshop on Graphs and Combinatorial Optimization (CTW), 2009, Paris, France. pp.19-22, 2009. <hal-00795413>

Partager

Métriques

Consultations de la notice

62