Matroid Tree-Width

Warning

This publication doesn't include Faculty of Economics and Administration. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

HLINĚNÝ Petr WHITTLE Geoff

Year of publication 2006
Type Article in Periodical
Magazine / Source European Journal of Combinatorics
MU Faculty or unit

Faculty of Informatics

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:

You are running an old browser version. We recommend updating your browser to its latest version.