Graphs of small rank-width are pivot-minors of graphs of small tree-width

DOI10.1016/J.DAM.2013.01.007MaRDI QIDQ2442212zbMATH OpenOpenAlexFDO

Authors O-joung Kwon, Sang-Il Oum

Publication date 2 April 2014

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1203.3606

zbMATH Keywords

distance-hereditarylinear rank-widthpath-widthpivot-minorrank-widthtree-widthvertex-minor

Mathematics Subject Classification ID

Distance in graphs (05C12)

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.

Recommendations

• Tree pivot-minors and linear rank-width
• Rank-width and vertex-minors
• Tree-depth and vertex-minors
• Rank-width and tree-width of \(H\)-minor-free graphs
• Rank connectivity and pivot-minors of graphs

Cites work

• Distance-hereditary graphs
• Graph minors. II. Algorithmic aspects of tree-width
• scientific article; zbMATH DE number 3156382 (Why is no real title available?)
• Isotropic systems
• Obstructions for linear rank-width at most 1
• Principal pivot transforms: Properties and applications
• Rank-width and vertex-minors
• Rank‐width is less than or equal to branch‐width
• Thread graphs, linear rank-width and their algorithmic applications
• Transforming trees by successive local complementations

Cited in

(16)

• Computing small pivot-minors
• Obstructions for bounded shrub-depth and rank-depth
• The complexity of the vertex-minor problem
• Rank connectivity and pivot-minors of graphs
• Rank-width: algorithmic and structural results
• Rank-width and vertex-minors
• Tree-depth and vertex-minors
• Excluding a bipartite circle graph from line graphs
• Tree pivot-minors and linear rank-width
• Coloring graphs without fan vertex-minors and graphs without cycle pivot-minors
• Rank‐width is less than or equal to branch‐width
• Graphs of bounded depth‐2 rank‐brittleness
• Vertex-minors of graphs: a survey
• Tree pivot-minors and linear rank-width
• Computing pivot-minors
• An overview of universal obstructions for graph parameters

This page was built for publication: Graphs of small rank-width are pivot-minors of graphs of small tree-width

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2442212)