Graphs of bounded depth-2 rank-brittleness

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 32
  • Download : 0
We characterize classes of graphs closed under taking vertex-minors and having noPnand no disjoint union ofncopies of the 1-subdivision ofK1,nfor somen. Our characterization is described in terms of a tree of radius 2 whose leaves are labeled by the vertices of a graphG, and the width is measured by the maximum possible cut-rank of a partition ofV(G)induced by splitting an internal node of the tree to make two components. The minimum width possible is called the depth-2 rank-brittleness ofG. We prove that for alln, every graph with sufficiently large depth-2 rank-brittleness containsPnor disjoint union ofncopies of the 1-subdivision ofK1,nas a vertex-minor.
Publisher
WILEY
Issue Date
2021-03
Language
English
Article Type
Article
Citation

JOURNAL OF GRAPH THEORY, v.96, no.3, pp.361 - 378

ISSN
0364-9024
DOI
10.1002/jgt.22619
URI
http://hdl.handle.net/10203/279999
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