BROWSE

Related Scientist

's photo.

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

ITEM VIEW & DOWNLOAD

Obstructions for bounded shrub-depth and rank-depth

DC Field Value Language
dc.contributor.authorO-joung Kwon-
dc.contributor.authorRose McCarty-
dc.contributor.authorSang-il Oum-
dc.contributor.authorPaul Wollan-
dc.date.accessioned2021-08-05T01:30:05Z-
dc.date.accessioned2021-08-05T01:30:05Z-
dc.date.available2021-08-05T01:30:05Z-
dc.date.available2021-08-05T01:30:05Z-
dc.date.created2021-02-23-
dc.date.issued2021-07-
dc.identifier.issn0095-8956-
dc.identifier.urihttps://pr.ibs.re.kr/handle/8788114/10028-
dc.description.abstractShrub-depth and rank-depth are dense analogues of the tree-depth of a graph. It is well known that a graph has large tree-depth if and only if it has a long path as a subgraph. We prove an analogous statement for shrub-depth and rank-depth, which was conjectured by Hlineny et al. (2016) [11]. Namely, we prove that a graph has large rank-depth if and only if it has a vertex-minor isomorphic to a long path. This implies that for every integer t, the class of graphs with no vertex-minor isomorphic to the path on t vertices has bounded shrub-depth. (C) 2021 Elsevier Inc. All rights reserved.-
dc.language영어-
dc.publisherACADEMIC PRESS INC ELSEVIER SCIENCE-
dc.titleObstructions for bounded shrub-depth and rank-depth-
dc.typeArticle-
dc.type.rimsART-
dc.identifier.wosid000642463700005-
dc.identifier.scopusid2-s2.0-85099798845-
dc.identifier.rimsid74520-
dc.contributor.affiliatedAuthorO-joung Kwon-
dc.contributor.affiliatedAuthorSang-il Oum-
dc.identifier.doi10.1016/j.jctb.2021.01.005-
dc.identifier.bibliographicCitationJOURNAL OF COMBINATORIAL THEORY SERIES B, v.149, pp.76 - 91-
dc.relation.isPartOfJOURNAL OF COMBINATORIAL THEORY SERIES B-
dc.citation.titleJOURNAL OF COMBINATORIAL THEORY SERIES B-
dc.citation.volume149-
dc.citation.startPage76-
dc.citation.endPage91-
dc.type.docTypeArticle-
dc.description.journalClass1-
dc.description.journalClass1-
dc.description.isOpenAccessN-
dc.description.journalRegisteredClassscie-
dc.description.journalRegisteredClassscopus-
dc.relation.journalResearchAreaMathematics-
dc.relation.journalWebOfScienceCategoryMathematics-
dc.subject.keywordPlusTREE-DEPTH-
dc.subject.keywordPlusVERTEX-MINORS-
dc.subject.keywordPlusCLIQUE-WIDTH-
dc.subject.keywordPlusGRAPHS-
dc.subject.keywordAuthorShrub-depth-
dc.subject.keywordAuthorRank-depth-
dc.subject.keywordAuthorVertex-minor-
dc.subject.keywordAuthorPivot-minor-
dc.subject.keywordAuthorPath-
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