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

2009/10/01 by Fedor V. Fomin, Sang-il Oum, Sang‐il Oum +1 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Bounded function #Combinatorics #Discrete mathematics #Graph #Graph theory and applications #Humanities #Limits and Structures in Graph Theory #Mathematical analysis #Mathematics #Minor (academic) #Rank (graph theory) #Tree (set theory) #math.CO #msc:05C10 #msc:05C78 #msc:05C8

paper · pdf · doi:10.1016/j.ejc.2010.05.003

published as European J. Combin. 31(2010 Oct)(7), pp. 1617-1628 · 17 pages

arxiv created 2009/10/01 · openalex publication_date 2010/06/01 · arxiv updated 2014/03/26 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/05

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.

Citations

• Upper bounds to the clique width of graphs
• Lower bound of the hadwiger number of graphs by their average degree
• The Extremal Function for Complete Minors
• An extremal function for contractions of graphs

Cited by

• Entanglement from Expansion: High Rank-Width in Deterministic Graphs
• Hadwiger number [wikipedia]

Related

• Catching Rats in H-minor-free Graphs
• A Note on Graphs of Linear Rank-Width 1
• Tree-width of a graph excluding an apex-forest or a wheel as a minor
• Graphs of Small Rank-width are Pivot-minors of Graphs of Small Tree-width
• Linear rank-width of distance-hereditary graphs II. Vertex-minor obstructions