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

DOI10.1016/j.dam.2013.01.007zbMath1285.05047arXiv1203.3606OpenAlexW1987986967MaRDI QIDQ2442212

Sang-il Oum, O-joung Kwon

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

tree-widthdistance-hereditarylinear rank-widthpath-widthpivot-minorrank-widthvertex-minor

Mathematics Subject Classification ID

Distance in graphs (05C12)

Related Items (6)

Tree-depth and vertex-minors ⋮ Rank-width: algorithmic and structural results ⋮ Coloring graphs without fan vertex-minors and graphs without cycle pivot-minors ⋮ Obstructions for bounded shrub-depth and rank-depth ⋮ The complexity of the vertex-minor problem ⋮ Tree Pivot-Minors and Linear Rank-Width

Cites Work

• Unnamed Item
• Distance-hereditary graphs
• Isotropic systems
• Principal pivot transforms: Properties and applications
• Obstructions for linear rank-width at most 1
• Rank-width and vertex-minors
• Thread Graphs, Linear Rank-Width and Their Algorithmic Applications
• Graph minors. II. Algorithmic aspects of tree-width
• Transforming trees by successive local complementations
• Rank‐width is less than or equal to branch‐width

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