BROWSE

Related Scientist

's photo.

수리 및 계산 과학 연구단
more info

ITEM VIEW & DOWNLOAD

TREE PIVOT-MINORS AND LINEAR RANK-WIDTH

Cited 0 time in webofscience Cited 0 time in scopus
84 Viewed 0 Downloaded
Title
TREE PIVOT-MINORS AND LINEAR RANK-WIDTH
Author(s)
Dabrowski, Konrad K.; Dross, Francois; Jeong, Jisu; Kante, Mamadou M.; O-joung Kwon; Sang-il Oum; Paulusma, Daniel
Publication Date
2021-08
Journal
SIAM JOURNAL ON DISCRETE MATHEMATICS, v.35, no.4, pp.2922 - 2945
Publisher
SIAM PUBLICATIONS
Abstract
Tree-width and its linear variant path-width play a central role for the graph minor relation. In particular, Robertson and Seymour [J. Combin. Theory Ser. B, 35 (1983), pp. 39--61] 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 = P-4 and T = K-1,K-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 (H-1, H-2)-free graphs, which we then show to have bounded linear rank-width. In particular, we prove that the class of (K-3, S-1,S-2,S-2)-free graphs has bounded linear rank-width, which strengthens a known result that this graph class has bounded rank-width.
URI
https://pr.ibs.re.kr/handle/8788114/11093
DOI
10.1137/21M1402339
ISSN
0895-4801
Appears in Collections:
Pioneer Research Center for Mathematical and Computational Sciences(수리 및 계산과학 연구단) > Discrete Mathematics Group(이산 수학 그룹) > 1. Journal Papers (저널논문)
Files in This Item:
There are no files associated with this item.

qrcode

  • facebook

    twitter

  • Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
해당 아이템을 이메일로 공유하기 원하시면 인증을 거치시기 바랍니다.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse