Graphs of Small Rank-width are Pivot-minors of Graphs of Small Tree-width

Abstract

We prove that every graph of rank-width $k$ is a pivot-minor of a graph of tree-width at most $2k$. We also prove that graphs of rank-width at most 1, equivalently distance-hereditary graphs, are exactly vertex-minors of trees, and graphs of linear rank-width at most 1 are precisely vertex-minors of paths. In addition, we show that bipartite graphs of rank-width at most 1 are exactly pivot-minors of trees and bipartite graphs of linear rank-width at most 1 are precisely pivot-minors of paths.

arXiv comment16 pages, 7 figures

Cited by in corpus (6)

• Rank-width: Algorithmic and structural results
• Obstructions for bounded shrub-depth and rank-depth
• Coloring graphs without fan vertex-minors and graphs without cycle pivot-minors
• A Note on Graphs of Linear Rank-Width 1
• Tree-depth and Vertex-minors
• Tree pivot-minors and linear rank-width