J 2016

Tree-depth and Vertex-minors

HLINĚNÝ, Petr, O-joung KWON, Jan OBDRŽÁLEK and Sebastian ORDYNIAK

Basic information

Original name

Tree-depth and Vertex-minors

Authors

HLINĚNÝ, Petr (203 Czech Republic, guarantor, belonging to the institution), O-joung KWON (410 Republic of Korea), Jan OBDRŽÁLEK (203 Czech Republic, belonging to the institution) and Sebastian ORDYNIAK (276 Germany, belonging to the institution)

Edition

European Journal of Combinatorics, Elsevier, 2016, 0195-6698

Other information

Language

English

Type of outcome

Článek v odborném periodiku

Field of Study

10101 Pure mathematics

Country of publisher

Netherlands

Confidentiality degree

není předmětem státního či obchodního tajemství

Impact factor

Impact factor: 0.786

RIV identification code

RIV/00216224:14330/16:00088544

Organization unit

Faculty of Informatics

DOI

UT WoS

000376056600004

Keywords in English

tree-depth; shrub-depth; vertex-minor; pivot-minor

Tags

Tags

International impact, Reviewed
Změněno: 17/4/2018 09:45, prof. RNDr. Petr Hliněný, Ph.D.

Abstract

ORIG CZ

V originále

In a recent paper Kwon and Oum (2014), Kwon and Oum claim that every graph of bounded rank-width is a pivot-minor of a graph of bounded tree-width (while the converse has been known true already before). We study the analogous questions for “depth” parameters of graphs, namely for the tree-depth and related new shrub-depth. We show how a suitable adaptation of known results implies that shrub-depth is monotone under taking vertex-minors, and we prove that every graph class of bounded shrub-depth can be obtained via vertex-minors of graphs of bounded tree-depth. While we exhibit an example that pivot-minors are generally not sufficient (unlike Kwon and Oum (2014)) in the latter statement, we then prove that the bipartite graphs in every class of bounded shrub-depth can be obtained as pivot-minors of graphs of bounded tree-depth.

In Czech

Dokazujeme, že každou třída grafů omezené shrub-depth lze získat pomocí vrcholových minorů z třídy omezené tree-depth. V obecnosti toto neplatí pro pivot minory.

Links

GA14-03501S, research and development project
Name: Parametrizované algoritmy a kernelizace v kontextu diskrétní matematiky a logiky
Investor: Czech Science Foundation