Article ID Journal Published Year Pages File Type
4654201 European Journal of Combinatorics 2010 12 Pages PDF
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
, , ,