| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4652570 | Electronic Notes in Discrete Mathematics | 2009 | 5 Pages |
Abstract
In Graph Minors III, Robertson and Seymour conjecture that the tree-width of a graph and that of its dual differ by at most one. In this paper, 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∗ minus one.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
