Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

Tree pivot-minors and linear rank-width

Dabrowski, K.K. and Dross, F. and Jeong, J. and Kante, M.M. and Kwon, O. and Oum, S. and Paulusma, D. (2021) 'Tree pivot-minors and linear rank-width.', SIAM journal on discrete mathematics., 35 (4). pp. 2922-2945.

Abstract

Tree-width and its linear variant path-width play a central role for the graph minor relation. In particular, Robertson and Seymour (1983) proved that for every tree T, the class of graphs that do not contain T as a minor has bounded path-width. For the pivot-minor relation, rank-width and linear rank-width take over the role of tree-width and path-width. As such, it is natural to examine if, for every tree T, the class of graphs that do not contain T as a pivot-minor has bounded linear rank-width. We first prove that this statement is false whenever T is a tree that is not a caterpillar. We conjecture that the statement is true if T is a caterpillar. We are also able to give partial confirmation of this conjecture by proving: • for every tree T, the class of T-pivot-minor-free distance-hereditary graphs has bounded linear rank-width if and only if T is a caterpillar; • for every caterpillar T on at most four vertices, the class of T-pivot-minor-free graphs has bounded linear rank-width. To prove our second result, we only need to consider T “ P4 and T “ K1,3, but we follow a general strategy: first we show that the class of T-pivot-minor-free graphs is contained in some class of pH1, H2q-free graphs, which we then show to have bounded linear rank-width. In particular, we prove that the class of pK3, S1,2,2q-free graphs has bounded linear rank-width, which strengthens a known result that this graph class has bounded rank-width.

Item Type:Article
Full text:(AM) Accepted Manuscript
Download PDF
(395Kb)
Status:Peer-reviewed
Publisher Web site:https://doi.org/10.1137/21M1402339
Date accepted:11 August 2021
Date deposited:24 August 2021
Date of first online publication:07 December 2021
Date first made open access:27 July 2022

Save or Share this output

Export:
Export
Look up in GoogleScholar