Skip to main content

Research Repository

Advanced Search

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



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.

Presentation Conference Type Conference Paper (Published)
Conference Name EuroComb 2019
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