We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Tree pivot-minors and linear rank-width.

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.


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
Full text:Publisher-imposed embargo
(VoR) Version of Record
File format - PDF
Publisher Web site:
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

Look up in GoogleScholar