BROWSE

Related Scientist

chakraborti,debsoumya's photo.

chakraborti,debsoumya
이산수학그룹
more info

ITEM VIEW & DOWNLOAD

RAINBOW SATURATION FOR COMPLETE GRAPHS

Cited 0 time in webofscience Cited 0 time in scopus
121 Viewed 0 Downloaded
Title
RAINBOW SATURATION FOR COMPLETE GRAPHS
Author(s)
Debsoumya Chakraborti; Kevin Hendrey; Ben Lund; Tompkins, Casey
Publication Date
2024-03
Journal
SIAM Journal on Discrete Mathematics, v.38, no.1, pp.1090 - 1112
Publisher
Society for Industrial and Applied Mathematics
Abstract
We call an edge-colored graph rainbow if all of its edges receive distinct colors. An edge-colored graph Gamma is called H-rainbow saturated if Gamma does not contain a rainbow copy of H and adding an edge of any color to Gamma creates a rainbow copy of H. The rainbow saturation number sat(n,R(H)) is the minimum number of edges in an n-vertex H-rainbow saturated graph. Gir & atilde;o, Lewis, and Popielarz conjectured that sat(n,R(K-r)) = 2(r-2)n + O(1) for fixed r >= 3. Disproving this conjecture, we establish that for every r >= 3, there exists a constant alpha(r) such that r + Omega(r(1/3))<= alpha(r )<= r + r(1/2) and sat(n,R(K-r)) = alpha(r)n+O(1). Recently, Behague, Johnston, Letzter, Morrison, and Ogden independently gave a slightly weaker upper bound which was sufficient to disprove the conjecture. They also introduced the weak rainbow saturation number and asked whether this is equal to the rainbow saturation number of K-r, since the standard weak saturation number of complete graphs equals the standard saturation number. Surprisingly, our lower bound separates the rainbow saturation number from the weak rainbow saturation number, answering this question in the negative. The existence of the constant K-r resolves another of their questions in the affirmative for complete graphs. Furthermore, we show that the conjecture of Gir & atilde;o, Lewis, and Popielarz is true if we have an additional assumption that the edge-colored K-r-rainbow saturated graph must be rainbow. As an ingredient of the proof, we study graphs which are K-r-saturated with respect to the operation of deleting one edge and adding two edges.
URI
https://pr.ibs.re.kr/handle/8788114/15117
DOI
10.1137/23M1565875
ISSN
0895-4801
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