Geodesic
On triangle-free graphs maximizing embeddings of bipartite graphs
Dmitriy Gorovoy1 ; Andrzej Grzesik1 ; Justyna Jaworska1
1Jagiellonian University
The electronic journal of combinatorics, Tome 31 (2024) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

In 1991 Győri, Pach, and Simonovits proved that for any bipartite graph $H$ containing a matching avoiding at most $1$ vertex, the maximum number of copies of $H$ in any large enough triangle-free graph is achieved in a balanced complete bipartite graph. In this paper we improve their result by showing that if $H$ is a bipartite graph containing a matching of size $x$ and at most $\frac{1}{2}\sqrt{x-1}$ unmatched vertices, then the maximum number of copies of $H$ in any large enough triangle-free graph is achieved in a complete bipartite graph. We also prove that such a statement cannot hold if the number of unmatched vertices is $\Omega(x)$.
DOI : 10.37236/12431
Classification : 05C60, 05C35
Mots-clés : maximum number of copies

Dmitriy Gorovoy  1   ; Andrzej Grzesik  1   ; Justyna Jaworska  1

1 Jagiellonian University 
@article{10_37236_12431,
     author = {Dmitriy Gorovoy and Andrzej Grzesik and Justyna Jaworska},
     title = {On triangle-free graphs maximizing embeddings of bipartite graphs},
     journal = {The electronic journal of combinatorics},
     year = {2024},
     volume = {31},
     number = {2},
     doi = {10.37236/12431},
     zbl = {1543.05137},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/12431/}
}
TY  - JOUR
AU  - Dmitriy Gorovoy
AU  - Andrzej Grzesik
AU  - Justyna Jaworska
TI  - On triangle-free graphs maximizing embeddings of bipartite graphs
JO  - The electronic journal of combinatorics
PY  - 2024
VL  - 31
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/12431/
DO  - 10.37236/12431
ID  - 10_37236_12431
ER  - 
%0 Journal Article
%A Dmitriy Gorovoy
%A Andrzej Grzesik
%A Justyna Jaworska
%T On triangle-free graphs maximizing embeddings of bipartite graphs
%J The electronic journal of combinatorics
%D 2024
%V 31
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/12431/
%R 10.37236/12431
%F 10_37236_12431
Dmitriy Gorovoy; Andrzej Grzesik; Justyna Jaworska. On triangle-free graphs maximizing embeddings of bipartite graphs. The electronic journal of combinatorics, Tome 31 (2024) no. 2. doi: 10.37236/12431

Cité par Sources :