BROWSE

Related Scientist

Jinha, Kim's photo.

Jinha, Kim
이산수학 그룹
more info

ITEM VIEW & DOWNLOAD

Rainbow independent sets on dense graph classes

Cited 0 time in webofscience Cited 0 time in scopus
294 Viewed 0 Downloaded
Title
Rainbow independent sets on dense graph classes
Author(s)
Jinha Kim; Minki Kim; O-joung Kwon
Publication Date
2022-05
Journal
Discrete Applied Mathematics, v.312, pp.45 - 51
Publisher
Elsevier B.V.
Abstract
© 2021 Elsevier B.V.Given a family I of independent sets in a graph, a rainbow independent set is an independent set I such that there is an injection ϕ:I→I where for each v∈I, v is contained in ϕ(v). Aharoni et al. (2019) determined for various graph classes C whether C satisfies a property that for every n, there exists N=N(C,n) such that every family of N independent sets of size n in a graph in C contains a rainbow independent set of size n. In this paper, we add two dense graph classes satisfying this property, namely, the class of graphs of bounded neighborhood diversity and the class of r-powers of graphs in a bounded expansion class.
URI
https://pr.ibs.re.kr/handle/8788114/11556
DOI
10.1016/j.dam.2021.04.007
ISSN
0166-218X
Appears in Collections:
Pioneer Research Center for Mathematical and Computational Sciences(수리 및 계산과학 연구단) > Discrete Mathematics Group(이산 수학 그룹) > 1. Journal Papers (저널논문)
Pioneer Research Center for Mathematical and Computational Sciences(수리 및 계산과학 연구단) > 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