Geodesic
Extremal results for graphs avoiding a rainbow subgraph
Zhen He1 ; Peter Frankl2 ; Ervin Győri2 ; Zequn Lv1 ; Nika Salia3 ; Casey Tompkins2 ; Kitti Varga4 ; Xiutao Zhu5
1Department of Mathematical Sciences, Tsinghua University
2Renyi Institute
3Institute for Basic Science, ECOPRO group
4Department of Computer Science and Information Theory, Budapest University of Technology and Economics
5Department of Mathematics, Nanjing University
The electronic journal of combinatorics, Tome 31 (2024) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

We say that $k$ graphs $G_1,G_2,\dots,G_k$ 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 $G_i$. 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.
DOI : 10.37236/11676
Classification : 05C35, 05C15
Mots-clés : Mantel's theorem, Turán graphs

Zhen He  1   ; Peter Frankl  2   ; Ervin Győri  2   ; Zequn Lv  1   ; Nika Salia  3   ; Casey Tompkins  2   ; Kitti Varga  4   ; Xiutao Zhu  5

1 Department of Mathematical Sciences, Tsinghua University
2 Renyi Institute
3 Institute for Basic Science, ECOPRO group
4 Department of Computer Science and Information Theory, Budapest University of Technology and Economics
5 Department of Mathematics, Nanjing University 
@article{10_37236_11676,
     author = {Zhen  He and Peter  Frankl and Ervin  Gy\H{o}ri and Zequn  Lv and Nika Salia and Casey Tompkins and Kitti  Varga and Xiutao  Zhu},
     title = {Extremal results for graphs avoiding a rainbow subgraph},
     journal = {The electronic journal of combinatorics},
     year = {2024},
     volume = {31},
     number = {1},
     doi = {10.37236/11676},
     zbl = {1533.05132},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/11676/}
}
TY  - JOUR
AU  - Zhen  He
AU  - Peter  Frankl
AU  - Ervin  Győri
AU  - Zequn  Lv
AU  - Nika Salia
AU  - Casey Tompkins
AU  - Kitti  Varga
AU  - Xiutao  Zhu
TI  - Extremal results for graphs avoiding a rainbow subgraph
JO  - The electronic journal of combinatorics
PY  - 2024
VL  - 31
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/11676/
DO  - 10.37236/11676
ID  - 10_37236_11676
ER  - 
%0 Journal Article
%A Zhen  He
%A Peter  Frankl
%A Ervin  Győri
%A Zequn  Lv
%A Nika Salia
%A Casey Tompkins
%A Kitti  Varga
%A Xiutao  Zhu
%T Extremal results for graphs avoiding a rainbow subgraph
%J The electronic journal of combinatorics
%D 2024
%V 31
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/11676/
%R 10.37236/11676
%F 10_37236_11676
Zhen  He; Peter  Frankl; Ervin  Győri; Zequn  Lv; Nika Salia; Casey Tompkins; Kitti  Varga; Xiutao  Zhu. Extremal results for graphs avoiding a rainbow subgraph. The electronic journal of combinatorics, Tome 31 (2024) no. 1. doi: 10.37236/11676

Cité par Sources :