Scattered classes of graphs
- Title
- Scattered classes of graphs
- Author
- 권오정
- Keywords
- graph structure; vertex-minor; subgraph
- Issue Date
- 2020-03
- Publisher
- SIAM PUBLICATIONS
- Citation
- SIAM JOURNAL ON DISCRETE MATHEMATICS, v. 34, no. 1, page. 972-999
- Abstract
- 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.
- URI
- https://epubs.siam.org/doi/10.1137/19M1293776https://repository.hanyang.ac.kr/handle/20.500.11754/169106
- ISSN
- 0895-4801; 1095-7146
- DOI
- 10.1137/19M1293776
- Appears in Collections:
- COLLEGE OF NATURAL SCIENCES[S](자연과학대학) > MATHEMATICS(수학과) > Articles
- Files in This Item:
There are no files associated with this item.
- Export
- RIS (EndNote)
- XLS (Excel)
- XML