Tree pivot-minors and linear rank-width

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

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, July). Tree pivot-minors and linear rank-width. Presented at EuroComb 2019, Bratislava, Slovakia

• 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