Matroid Tree-Width
| Authors | |
|---|---|
| Year of publication | 2006 |
| Type | Article in Periodical |
| Magazine / Source | European Journal of Combinatorics |
| MU Faculty or unit | |
| Citation | |
| web | doi |
| Field | General mathematics |
| Keywords | graph; matroid; tree-width; branch-width |
| Description | We show that the tree-width of a graph can be defined without reference to graph vertices, and hence the notion of tree-width can be naturally extended to matroids. (This extension was inspired by an original unpublished idea of Jim Geelen.) We prove that the tree-width of a graphic matroid is equal to that of its underlying graph. Furthermore, we extend the well-known relation between the branch-width and the tree-width of a graph to all matroids. |
| Related projects: |