1Department of Computer Science, Durham University, UK 2Université Côte d'Azur, I3S, CNRS, Inria, France 3Department of Mathematical Sciences, KAIST, Korea 4Université Clermont Auvergne, LIMOS, CNRS, Aubière, France 5Department of Mathematics, Incheon National University, Korea 6Discrete Mathematics Group, Institute for Basic Science (IBS) and Department of Mathematical Sciences, KAIST, Korea
Acta mathematica Universitatis Comenianae, Tome 88 (2019) no. 3, pp. 577-583
Citer cet article
Konrad K. Dabrowski; François Dross; Jisu Jeong; Mamadou Moustapha Kanté; O-joung Kwon; Sang-il Oum; Daniël Paulusma; Konrad K. Dabrowski; François Dross; Jisu Jeong; Mamadou Moustapha Kanté; O-joung Kwon; Sang-il Oum; Daniël Paulusma. Tree pivot-minors and linear rank-width. Acta mathematica Universitatis Comenianae, Tome 88 (2019) no. 3, pp. 577-583. http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a35/
@article{AMUC_2019_88_3_a35,
author = {Konrad K. Dabrowski and Fran\c{c}ois Dross and Jisu Jeong and Mamadou Moustapha Kant\'e and O-joung Kwon and Sang-il Oum and Dani\"el Paulusma and Konrad K. Dabrowski and Fran\c{c}ois Dross and Jisu Jeong and Mamadou Moustapha Kant\'e and O-joung Kwon and Sang-il Oum and Dani\"el Paulusma},
title = { Tree pivot-minors and linear rank-width},
journal = {Acta mathematica Universitatis Comenianae},
pages = {577--583},
year = {2019},
volume = {88},
number = {3},
url = {http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a35/}
}
TY - JOUR
AU - Konrad K. Dabrowski
AU - François Dross
AU - Jisu Jeong
AU - Mamadou Moustapha Kanté
AU - O-joung Kwon
AU - Sang-il Oum
AU - Daniël Paulusma
AU - Konrad K. Dabrowski
AU - François Dross
AU - Jisu Jeong
AU - Mamadou Moustapha Kanté
AU - O-joung Kwon
AU - Sang-il Oum
AU - Daniël Paulusma
TI - Tree pivot-minors and linear rank-width
JO - Acta mathematica Universitatis Comenianae
PY - 2019
SP - 577
EP - 583
VL - 88
IS - 3
UR - http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a35/
ID - AMUC_2019_88_3_a35
ER -
%0 Journal Article
%A Konrad K. Dabrowski
%A François Dross
%A Jisu Jeong
%A Mamadou Moustapha Kanté
%A O-joung Kwon
%A Sang-il Oum
%A Daniël Paulusma
%A Konrad K. Dabrowski
%A François Dross
%A Jisu Jeong
%A Mamadou Moustapha Kanté
%A O-joung Kwon
%A Sang-il Oum
%A Daniël Paulusma
%T Tree pivot-minors and linear rank-width
%J Acta mathematica Universitatis Comenianae
%D 2019
%P 577-583
%V 88
%N 3
%U http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a35/
%F AMUC_2019_88_3_a35
Treewidth and its linear variant path-width play a central role for the graph minor relation. Rank-width and linear rank-width do the same for the graph pivot-minor relation. Robertson and Seymour (1983) proved that for every tree T there exists a constant cT such that every graph of path-width at least cT contains T as a minor. Motivated by this result, we examine whether for every tree T there exists a constant dT such that every graph of linear rank-width at least dT contains T as a pivot-minor. We show that this is false if T is not a caterpillar, but true if T is the claw.
