Dabrowski, K.K. and Dross, F. and Jeong, J. and Kanté, M.M. and Kwon, O. and Oum, S. and Paulusma, D. (2019) 'Tree pivot-minors and linear rank-width.', Acta Mathematica Universitatis Comenianae., 88 (3). pp. 577-583.
Abstract
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.
Item Type: | Article |
---|---|
Full text: | Publisher-imposed embargo (AM) Accepted Manuscript File format - PDF (237Kb) |
Full text: | Publisher-imposed embargo (VoR) Version of Record File format - PDF (235Kb) |
Status: | Peer-reviewed |
Publisher Web site: | http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/index |
Date accepted: | 07 May 2019 |
Date deposited: | 13 June 2019 |
Date of first online publication: | 29 July 2019 |
Date first made open access: | No date available |
Save or Share this output
Export: | |
Look up in GoogleScholar |