BROWSE

Related Scientist

Oum, Sang-il's photo.

Oum, Sang-il
이산수학 그룹
more info

ITEM VIEW & DOWNLOAD

Obstructions for partitioning into forests and outerplanar graphs

Cited 0 time in webofscience Cited 0 time in scopus
144 Viewed 0 Downloaded
Title
Obstructions for partitioning into forests and outerplanar graphs
Author(s)
Ringi Kim; Sergey Norin; Sang-il Oum
Publication Date
2022-05
Journal
DISCRETE APPLIED MATHEMATICS, v.312, pp.15 - 28
Publisher
ELSEVIER SCIENCE BV
Abstract
For a class C of graphs, we define C-edge-brittleness of a graph G as the minimum ℓ such that the vertex set of G can be partitioned into sets inducing a subgraph in C and there are ℓ edges having ends in distinct parts. We characterize classes of graphs having bounded C-edge-brittleness for a class C of forests or a class C of graphs with no K4∖e topological minors in terms of forbidden obstructions. We also define C-vertex-brittleness of a graph G as the minimum ℓ such that the edge set of G can be partitioned into sets inducing a subgraph in C and there are ℓ vertices incident with edges in distinct parts. We characterize classes of graphs having bounded C-vertex-brittleness for a class C of forests or a class C of outerplanar graphs in terms of forbidden obstructions. We also investigate the relations between the new parameters and the edit distance
URI
https://pr.ibs.re.kr/handle/8788114/11557
DOI
10.1016/j.dam.2020.09.006
ISSN
0166-218X
Appears in Collections:
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