Tree-width of hypergraphs and surface duality

2008/12/16 by Frédéric Mazoit, Mazoit, Frédéric
Computer Science · #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.DM

paper · pdf · doi:10.48550/arxiv.0812.2990

arxiv created 2008/12/16 · arxiv updated 2009/12/01

Abstract

In Graph Minor III, Robertson and Seymour conjecture that the tree-width of a planar graph and that of its dual differ by at most one. We prove that given a hypergraph H on a surface of Euler genus k, the tree-width of H^* is at most the maximum of tw(H) + 1 + k and the maximum size of a hyperedge of H^*.

Related

• Tree-width of hypergraphs and surface duality
• A simple proof of the tree-width duality theorem
• Tree-width of a graph excluding an apex-forest or a wheel as a minor
• Branchwidth is (1,g)-self-dual
• Twin-width of graphs on surfaces