BROWSE

Related Scientist

Jinha, Kim's photo.

Jinha, Kim
이산수학 그룹
more info

ITEM VIEW & DOWNLOAD

Badges and rainbow matchings

Cited 0 time in webofscience Cited 0 time in scopus
20 Viewed 0 Downloaded
Title
Badges and rainbow matchings
Author(s)
Aharoni, Ron; Briggs, Joseph; Jinha Kim; Minki Kim
Publication Date
2021-06
Journal
DISCRETE MATHEMATICS, v.344, no.6
Publisher
ELSEVIER
Abstract
© 2021 Elsevier B.V. All rights reserved. Drisko proved that 2n - 1 matchings of size n in a bipartite graph have a rainbow matching of size n. For general graphs it is conjectured that 2n matchings suffice for this purpose (and that 2n- 1 matchings suffice when n is even). The known graphs showing sharpness of this conjecture for n even are called badges. We improve the previously best known bound from 3n- 2 to 3n- 3, using a new line of proof that involves analysis of the appearance of badges. We also prove a ``cooperative'' generalization: for t > 0 and n >= 3, any 3n - 4 + t sets of edges, the union of every t of which contains a matching of size n, have a rainbow matching of size n.
URI
https://pr.ibs.re.kr/handle/8788114/10032
DOI
10.1016/j.disc.2021.112363
ISSN
0012-365X
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