Tree Pivot-Minors and Linear Rank-Width

Autor: Konrad K. Dabrowski, François Dross, Jisu Jeong, Mamadou M. Kanté, O-joung Kwon, Sang-il Oum, Daniël Paulusma

Publikováno v: Scopus-Elsevier
SIAM journal on discrete mathematics, 2021, Vol.35(4), pp.2922-2945 [Peer Reviewed Journal]
SIAM Journal on Discrete Mathematics
SIAM Journal on Discrete Mathematics, 2021, 35 (4), pp.2922-2945. ⟨10.1137/21M1402339⟩

Tree-width and its linear variant path-width play a central role for the graph minor relation. In particular, Robertson and Seymour (1983) proved that for every tree~$T$, the class of graphs that do not contain $T$ as a minor has bounded path-width.

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::15133ded7c08377859a9c00d2d90405d
https://eprints.whiterose.ac.uk/177573/1/treepivot.pdf