BROWSE

Related Scientist

's photo.

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

ITEM VIEW & DOWNLOAD

Obstructions for bounded shrub-depth and rank-depth

Cited 0 time in webofscience Cited 0 time in scopus
17 Viewed 0 Downloaded
Title
Obstructions for bounded shrub-depth and rank-depth
Author(s)
O-joung Kwon; Rose McCarty; Sang-il Oum; Paul Wollan
Publication Date
2021-07
Journal
JOURNAL OF COMBINATORIAL THEORY SERIES B, v.149, pp.76 - 91
Publisher
ACADEMIC PRESS INC ELSEVIER SCIENCE
Abstract
Shrub-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.
URI
https://pr.ibs.re.kr/handle/8788114/10028
DOI
10.1016/j.jctb.2021.01.005
ISSN
0095-8956
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