pith. sign in

arxiv: 0812.2990 · v1 · submitted 2008-12-16 · 💻 cs.DM

Tree-width of hypergraphs and surface duality

classification 💻 cs.DM
keywords tree-widthgraphmaximumsurfaceconjecturedifferdualduality
0
0 comments X
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.