Publication details

Dabrowski, 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

• Professor Daniel Paulusma
• Dr Konrad Dabrowski

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.