Rank-width and tree-width of H-minor-free graphs

Fedor V. Fomin, Sang Il Oum, Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review


We prove that for any fixed r≥2, the tree-width of graphs not containing Kr 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 Kr-minor free graphs and graphs of bounded genus.

Original languageEnglish (US)
Pages (from-to)1617-1628
Number of pages12
JournalEuropean Journal of Combinatorics
Issue number7
StatePublished - Oct 2010

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Rank-width and tree-width of H-minor-free graphs'. Together they form a unique fingerprint.

Cite this