Publication detailsDabrowski, K.K. , Dross, F. Jeong, J. Kanté, M.M. Kwon, O. Oum, S. & Paulusma, D. (2019), Tree pivot-minors and linear rank-width, 88: EuroComb 2019. Bratislava, Slovakia, Comenius University Press, 577-583.
- Publication type: Conference Paper
- ISSN/ISBN: 0862-9544
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
Author(s) from Durham
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.