BROWSE

Related Scientist

Chakraborti, Debsoumya's photo.

Chakraborti, Debsoumya
이산수학 그룹
more info

ITEM VIEW & DOWNLOAD

On a rainbow extremal problem for color-critical graphs

Cited 0 time in webofscience Cited 0 time in scopus
83 Viewed 0 Downloaded
Title
On a rainbow extremal problem for color-critical graphs
Author(s)
Debsoumya Chakraborti; Kim, Jaehoon; Lee, Hyunwoo; Hong Liu; Seo, Jaehyeon
Publication Date
2024-03
Journal
Random Structures and Algorithms, v.64, no.2, pp.460 - 489
Publisher
John Wiley and Sons Ltd
Abstract
Given (Formula presented.) graphs (Formula presented.) over a common vertex set of size (Formula presented.), what is the maximum value of (Formula presented.) having no “colorful” copy of (Formula presented.), that is, a copy of (Formula presented.) containing at most one edge from each (Formula presented.) ? Keevash, Saks, Sudakov, and Verstraëte denoted this number as (Formula presented.) and completely determined (Formula presented.) for large (Formula presented.). In fact, they showed that, depending on the value of (Formula presented.), one of the two natural constructions is always the extremal construction. Moreover, they conjectured that the same holds for every color-critical graphs, and proved it for 3-color-critical graphs. They also asked to classify the graphs (Formula presented.) that have only these two extremal constructions. We prove their conjecture for 4-color-critical graphs and for almost all (Formula presented.) -color-critical graphs when (Formula presented.). Moreover, we show that for every non-color-critical non-bipartite graphs, none of the two natural constructions is extremal for certain values of (Formula presented.). © 2023 Wiley Periodicals LLC.
URI
https://pr.ibs.re.kr/handle/8788114/14736
DOI
10.1002/rsa.21189
ISSN
1042-9832
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