BROWSE

Related Scientist

's photo.

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

ITEM VIEW & DOWNLOAD

TREE PIVOT-MINORS AND LINEAR RANK-WIDTH

DC Field Value Language
dc.contributor.authorDabrowski, Konrad K.-
dc.contributor.authorDross, Francois-
dc.contributor.authorJeong, Jisu-
dc.contributor.authorKante, Mamadou M.-
dc.contributor.authorO-joung Kwon-
dc.contributor.authorSang-il Oum-
dc.contributor.authorPaulusma, Daniel-
dc.date.accessioned2022-01-17T00:30:14Z-
dc.date.available2022-01-17T00:30:14Z-
dc.date.created2022-01-12-
dc.date.issued2021-08-
dc.identifier.issn0895-4801-
dc.identifier.urihttps://pr.ibs.re.kr/handle/8788114/11093-
dc.description.abstractTree-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.-
dc.language영어-
dc.publisherSIAM PUBLICATIONS-
dc.titleTREE PIVOT-MINORS AND LINEAR RANK-WIDTH-
dc.typeArticle-
dc.type.rimsART-
dc.identifier.wosid000736744500026-
dc.identifier.scopusid2-s2.0-85149441266-
dc.identifier.rimsid77075-
dc.contributor.affiliatedAuthorO-joung Kwon-
dc.contributor.affiliatedAuthorSang-il Oum-
dc.identifier.doi10.1137/21M1402339-
dc.identifier.bibliographicCitationSIAM JOURNAL ON DISCRETE MATHEMATICS, v.35, no.4, pp.2922 - 2945-
dc.relation.isPartOfSIAM JOURNAL ON DISCRETE MATHEMATICS-
dc.citation.titleSIAM JOURNAL ON DISCRETE MATHEMATICS-
dc.citation.volume35-
dc.citation.number4-
dc.citation.startPage2922-
dc.citation.endPage2945-
dc.description.journalClass1-
dc.description.journalClass1-
dc.description.isOpenAccessN-
dc.description.journalRegisteredClassscie-
dc.description.journalRegisteredClassscopus-
dc.relation.journalWebOfScienceCategoryMathematics, Applied-
dc.subject.keywordPlusCLIQUE-WIDTH-
dc.subject.keywordPlusGRAPH MINORS-
dc.subject.keywordPlusPARTITIONING PROBLEMS-
dc.subject.keywordPlusBIPARTITE GRAPHS-
dc.subject.keywordPlusCIRCLE GRAPH-
dc.subject.keywordAuthortree-
dc.subject.keywordAuthorpivot-minor-
dc.subject.keywordAuthorlinear rank-width-
Appears in Collections:
Pioneer Research Center for Mathematical and Computational Sciences(수리 및 계산과학 연구단) > 1. Journal Papers (저널논문)
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