Extremal Results for Graphs Avoiding a Rainbow Subgraph

被引：3

作者：

He, Zhen ^{[1
,2
]}

Frankl, Peter ^{[2
]}

Gyori, Ervin ^{[2
]}

Lv, Zequn ^{[3
]}

Salia, Nika ^{[2
,4
]}

Tompkins, Casey ^{[2
]}

Varga, Kitti ^{[2
,5
]}

Zhu, Xiutao

机构：

[1] Beijing Jiaotong Univ, Sch Math & Stat, Beijing, Peoples R China

[2] Hungarian Acad Sci, Alfred Renyi Inst Math, Budapest, Hungary

[3] Tsinghua Univ, Dept Math Sci, Beijing, Peoples R China

[4] King Fahd Univ Petr & Minerals, Dhahran, Saudi Arabia

[5] Tech Univ Budapest, Dept Comp Sci & Informat Theory, Budapest, Hungary

来源：

ELECTRONIC JOURNAL OF COMBINATORICS | 2024年 / 31卷 / 01期

关键词：

D O I：

10.37236/11676

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We say that k graphs G1, G2, ... , Gk on a common vertex set of size n contain a rainbow copy of a graph H if their union contains a copy of H with each edge belonging to a distinct Gi. We provide a counterexample to a conjecture of Frankl on the maximum product of the sizes of the edge sets of three graphs avoiding a rainbow triangle. We propose an alternative conjecture, which we prove under the additional assumption that the union of the three graphs is complete. Furthermore, we determine the maximum product of the sizes of the edge sets of three graphs or four graphs avoiding a rainbow path of length three.

引用

页数：11

共 9 条

[1]

Aharoni R., 2020, Advances in Combinatorics, V2020, P2

[2]

Babiński S, 2024, Arxiv, DOI arXiv:2211.02308

[3]

Chakraborti D, 2022, Arxiv, DOI arXiv:2204.02575

[4]

Diwan A., 2006, Turan's theorem with colors

[5]

Frankl P, 2022, Arxiv, DOI arXiv:2203.07768

[6]

HILTON AJW, 1977, J LOND MATH SOC, V15, P369

[7] Multicolour turan problems [J].

Keevash, P ;

Saks, M ;

Sudakov, B ;

Verstraëte, J .

ADVANCES IN APPLIED MATHEMATICS, 2004, 33 (02) :238-262

[8]

Mantel W., 1907, Wiskundige Opgaven, V10, P60

[9]

Turan P., 1941, Kozepisk. Mat. es Fiz. Lapok, V48, P436

← 1 →