Cookies

We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Research & business

View Profile

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.

Author(s) from Durham

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.