Tree pivot-minors and linear rank-width

Dabrowski, K.K.; Dross, F.; Jeong, J.; Kanté, M.M.; Kwon, O.; Oum, S.; Paulusma, D.

Tree pivot-minors and linear rank-width

Dabrowski, K.K.; Dross, F.; Jeong, J.; Kanté, M.M.; Kwon, O.; Oum, S.; Paulusma, D.

Authors

K.K. Dabrowski

F. Dross

J. Jeong

M.M. Kanté

O. Kwon

S. Oum

Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor

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.

Citation

Dabrowski, K., Dross, F., Jeong, J., Kanté, M., Kwon, O., Oum, S., & Paulusma, D. (2019). Tree pivot-minors and linear rank-width.

Conference Name	EuroComb 2019
Conference Location	Bratislava, Slovakia
Acceptance Date	May 7, 2019
Online Publication Date	Jul 29, 2019
Publication Date	Jul 29, 2019
Deposit Date	Jun 12, 2019
Volume	88
Pages	577-583
Series Number	3
Series ISSN	0862-9544
Public URL	https://durham-repository.worktribe.com/output/1142670
Publisher URL	http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/index