TREE PIVOT-MINORS AND LINEAR RANK-WIDTH

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 21
  • Download : 0
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 c(T) such that every graph of path-width at least c(T) contains T as a minor. Motivated by this result, we examine whether for every tree T there exists a constant d(T) such that every graph of linear rank-width at least d(T) 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.
Publisher
COMENIUS UNIV
Issue Date
2019-09
Language
English
Article Type
Article
Citation

ACTA MATHEMATICA UNIVERSITATIS COMENIANAE, v.88, no.3, pp.577 - 583

ISSN
0231-6986
URI
http://hdl.handle.net/10203/267659
Appears in Collection
MA-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0