Tree pivot-minors and linear rank-width

Main Article Content

Konrad K. Dabrowski François Dross Jisu Jeong Mamadou Moustapha Kanté O-joung Kwon Sang-il Oum Daniël Paulusma


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.

Article Details

How to Cite
Dabrowski, K., Dross, F., Jeong, J., Kanté, M., Kwon, O., Oum, S., & Paulusma, D. (2019). Tree pivot-minors and linear rank-width. Acta Mathematica Universitatis Comenianae, 88(3), 577-583. Retrieved from