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.
Obstructions for bounded shrub-depth and rank-depth / Kwon, O. -J.; Mccarty, R.; Oum, S. -I.; Wollan, P.. - In: JOURNAL OF COMBINATORIAL THEORY. - ISSN 0095-8956. - 149:(2021), pp. 76-91. [10.1016/j.jctb.2021.01.005]
Obstructions for bounded shrub-depth and rank-depth
Wollan P.
2021
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
