BROWSE

Related Scientist

's photo.

수리 및 계산 과학 연구단
more info

ITEM VIEW & DOWNLOAD

Scattered Classes of Graphs

Cited 0 time in webofscience Cited 0 time in scopus
52 Viewed 0 Downloaded
Title
Scattered Classes of Graphs
Author(s)
O-joung Kwon; Sang-il Oum
Publication Date
2020-03
Journal
SIAM Journal on Discrete Mathematics, v.34, no.1, pp.972 - 999
Publisher
Society for Industrial and Applied Mathematics
Abstract
Abstract. For a class C of graphs G equipped with functions fG dened on subsets of EpGq or V pGq, we say that C is k-scattered with respect to fG if there exists a constant ` such that for every graph G P C, the domain of fG can be partitioned into subsets of size at most k so that the union of every collection of the subsets has fG 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 mK1;n vertex-minor, which allows us to prove that such graphs have bounded linear rank-width.
URI
https://pr.ibs.re.kr/handle/8788114/12413
DOI
10.1137/19M1293776
ISSN
0895-4801
Appears in Collections:
Pioneer Research Center for Mathematical and Computational Sciences(수리 및 계산과학 연구단) > 1. Journal Papers (저널논문)
Pioneer Research Center for Mathematical and Computational Sciences(수리 및 계산과학 연구단) > Discrete Mathematics Group(이산 수학 그룹) > 1. Journal Papers (저널논문)
Files in This Item:
There are no files associated with this item.

qrcode

  • facebook

    twitter

  • Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
해당 아이템을 이메일로 공유하기 원하시면 인증을 거치시기 바랍니다.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse