Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4654201 | European Journal of Combinatorics | 2010 | 12 Pages |
Abstract
We prove that for any fixed r≥2r≥2, the tree-width of graphs not containing KrKr as a topological minor (resp. as a subgraph) is bounded by a linear (resp. polynomial) function of their rank-width. We also present refinements of our bounds for other graph classes such as KrKr-minor free graphs and graphs of bounded genus.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Fedor V. Fomin, Sang-il Oum, Dimitrios M. Thilikos,