Tree pivot-minors and linear rank-width - Dabrowski, K.K.; Dross, F.; Jeong, J.; Kanté, M.M.; Kwon, O.; Oum, S.; Paulusma, D. (2019)
Treewidth and its linear variant path-width play a central role for the graph minor relation. Rank-width and linear rank-width do the same for the graph pivot-minor relation. Robertson and Seymour (1983) proved that for every tree T there exists a constant cT such that every graph of path-width at least cT contains T as a minor. Motivated by this result, we examine whether for every tree T there exists a constant dT such that every graph of linear rank-width at least dT contains T as a pivot-minor. We show that this is false if T is not a caterpillar, but true if T is the claw.
EPrint Processing Status: DRO Team waiting for permission from publisher to deposit full text