Tree-width of hypergraphs and surface duality
classification
💻 cs.DM
keywords
tree-widthgraphmaximumsurfaceconjecturedifferdualduality
read the original 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^*.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.