On a rainbow extremal problem for color-critical graphs

被引:5
作者
Chakraborti, Debsoumya [1 ]
Kim, Jaehoon [2 ]
Lee, Hyunwoo [2 ]
Liu, Hong [3 ]
Seo, Jaehyeon [4 ]
机构
[1] Inst Basic Sci IBS, Discrete Math Grp DIMAG, Daejeon, South Korea
[2] KAIST Daejeon, Dept Math Sci, Daejeon, South Korea
[3] Inst Basic Sci IBS, Extremal Combinator & Probabil Grp ECOPRO, Daejeon, South Korea
[4] Yonsei Univ, Dept Math, Seoul, South Korea
基金
英国科研创新办公室; 新加坡国家研究基金会;
关键词
color-critical graphs; rainbow extremal problem;
D O I
10.1002/rsa.21189
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
Given k graphs G(1), ... ,G(k) over a common vertex set of size n, what is the maximum value of Sigma(i is an element of[k])e(G(i)) having no "colorful" copy of H, that is, a copy of H containing at most one edge from each G(i)? Keevash, Saks, Sudakov, and Verstraete denoted this number as ex(k)(n,H) and completely determined ex(k)(n,K-r) for large n. In fact, they showed that, depending on the value of k, 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 H that have only these two extremal constructions. We prove their conjecture for 4-color-critical graphs and for almost all 4-color-critical graphs when r > 4. Moreover, we show that for every non-color-critical non-bipartite graphs, none of the two natural constructions is extremal for certain values of k.
引用
收藏
页码:460 / 489
页数:30
相关论文
共 17 条
[1]  
Aharoni R., 2020, Adv. Combin., V2020, P2
[2]   A Rainbow r-Partite Version of the Erdos-Ko-Rado Theorem [J].
Aharoni, Ron ;
Howard, David .
COMBINATORICS PROBABILITY & COMPUTING, 2017, 26 (03) :321-337
[3]   A GENERALIZATION OF CARATHEODORYS THEOREM [J].
BARANY, I .
DISCRETE MATHEMATICS, 1982, 40 (2-3) :141-152
[4]  
Chakraborti D., RAINBOW EXTREMAL PRO
[5]  
Cheng Y., RAINBOW SPANNING STR
[6]  
Euler L, 1782, Verh. Zeeuwsch. Gennot. Wet. Vliss.
[7]  
Frankl P., GRAPHS RAINBOW TRIAN
[8]   On a rainbow version of Dirac's theorem [J].
Joos, Felix ;
Kim, Jaehoon .
BULLETIN OF THE LONDON MATHEMATICAL SOCIETY, 2020, 52 (03) :498-504
[9]   A topological colorful Helly theorem [J].
Kalai, G ;
Meshulam, R .
ADVANCES IN MATHEMATICS, 2005, 191 (02) :305-311
[10]  
Kalai G., COLORFUL CARATHEODOR