Scattered Classes of Graphs

Cited 1 time in webofscience Cited 0 time in scopus
  • Hit : 69
  • Download : 0
For a class C of graphs G equipped with functions f(G) defined on subsets of E(G) or V (G), we say that C is k-scattered with respect to f(G) if there exists a constant .e such that for every graph G is an element of C, the domain of f(G) can be partitioned into subsets of size at most k so that the union of every collection of the subsets has f(G) value at most We present structural characterizations of graph classes that are k-scattered with respect to several graph connectivity functions. In particular, our theorem for cut-rank functions provides a rough structural characterization of graphs having no mK(1,n) vertex-minor, which allows us to prove that such graphs have bounded linear rank-width.
Publisher
SIAM PUBLICATIONS
Issue Date
2020-01
Language
English
Article Type
Article
Citation

SIAM JOURNAL ON DISCRETE MATHEMATICS, v.34, no.1, pp.972 - 999

ISSN
0895-4801
DOI
10.1137/19m1293776
URI
http://hdl.handle.net/10203/275658
Appears in Collection
MA-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 1 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0