2012/03/31 by O-joung Kwon, Sang-il Oum · 1 citation
Mathematics · Computer Science · #math.CO #cs.DM
paper · pdf · doi:10.1016/j.dam.2013.01.007
published as Discrete Applied Math. 168(May 11, 2014), pp. 108-118 · 16 pages, 7 figures
arxiv created 2012/12/27 · arxiv updated 2014/03/26
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.