Rank-width and Tree-width of H-minor-free Graphs

Abstract

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

17 pages

References in corpus (1)

• The maximum number of cliques in a graph embedded in a surface

Cited by in corpus (10)

• Rank-width: Algorithmic and structural results
• Subgraph densities in a surface
• The maximum number of cliques in a graph embedded in a surface
• Number of cliques in graphs with a forbidden subdivision
• Tree densities in sparse graph classes
• Linear Kernels on Graphs Excluding Topological Minors
• Data-compression for Parametrized Counting Problems on Sparse graphs
• Cliques in Odd-Minor-Free Graphs
• On the number of cliques in graphs with a forbidden subdivision or immersion
• On the number of cliques in graphs with a forbidden minor