BZPEER

preprint2026arXiv

The maximum number of triangles in graphs without the square of a path

The generalized Turán number for $H$ of $G$ , denoted by $\ex(n,H,G)$, is the maximum number of copies of $H$ in an $n$ -vertex $G$ -free graph. When $H$ is an edge, $\ex(n,H,G)$ is the classical Turán number $\ex(n,G)$. Let $P_k$ be the path with $k$ vertices. The square of $P_k$ , denoted by $P_k^2$ , is obtained by joining the pairs of vertices with distance at most two in $P_k$ . The Turán number of $P_k^2$ , $\ex(n, P_k^2)$, was determined by several researchers. When $k=3$ , $P_3^2$ is the triangle and $\ex(n, P_3^2)$ is well-known from Mantel's theorem. When $k=4$ , $\ex(n, P_4^2)$ was solved by Dirac in a more general context. When $k=5,6$ , the problem was solved by Xiao, Katona, Xiao, and Zamora. For general $k \ge 7$ , the problem was solved by Yuan in a more general context. Recently, Mukherjee determined the generalized Turán number $\ex(n, K_3, P_5^2)$. In this paper, we determine the exact value of $\ex(n, K_3, P_6^2)$ and characterize all the extremal graphs for $n \ge 11$ .

preprint2022arXiv

Exact results for generalized extremal problems forbidding an even cycle

We determine the maximum number of copies of $K_{s,s}$ in a $C_{2s+2}$ -free $n$ -vertex graph for all integers $s \ge 2$ and sufficiently large $n$ . Moreover, for $s\in\{2,3\}$ and any integer $n$ we obtain the maximum number of cycles of length $2s$ in an $n$ -vertex $C_{2s+2}$ -free bipartite graph.

preprint2022arXiv

Extremal planar graphs with no cycles of particular lengths

In this paper we estimate the planar Turán number $\mathrm{ex}_\mathcal{P}(n,H)$ of some graphs $H$ , i.e., the maximum number of edges in a planar graph $G$ of $n$ vertices not containing $H$ as a subgraph. We give a new, short proof when $H=C_5$ , and study the cases when $G$ is bipartite or triangle-free and $H$ is a short even cycle. The proofs are mostly new applications or variants of the "contribution method" introduced by Ghosh, Győri, Martin, Paulos and Xiao in arXiv:2004.14094.

preprint2022arXiv

Planar Turán Number of Double Stars

Given a graph $F$ , the planar Turán number of $F$ , denoted $\text{ex}_{\mathcal{P}}(n, F)$ , is the maximum number of edges in an $n$ -vertex $F$ -free planar graph. Such an extremal graph problem was initiated by Dowden while determining sharp upper bound for $\text{ex}_{\mathcal{P}}(n,C_4)$ and $\text{ex}_{\mathcal{P}}(n,C_5)$ , where $C_4$ and $C_5$ are cycles of length four and five respectively. In this paper we determined an upper bound for $\text{ex}_{\mathcal{P}}(n,S_{2,2})$ , $\text{ex}_{\mathcal{P}}(n,S_{2,3})$ , $\text{ex}_{\mathcal{P}}(n,S_{2,4})$ , $\text{ex}_{\mathcal{P}}(n,S_{2,5})$ , $\text{ex}_{\mathcal{P}}(n,S_{3,3})$ and $\text{ex}_{\mathcal{P}}(n,S_{3,4})$ , where $S_{m,n}$ is a double star with $m$ and $n$ leafs. Moreover, the bounds for $\text{ex}_{\mathcal{P}}(n,S_{2,2})$ and $\text{ex}_{\mathcal{P}}(n,S_{2,3})$ are sharp.

preprint2022arXiv

Stability version of Dirac's theorem and its applications for generalized Turán problems

In 1952, Dirac proved that every $2$ -connected $n$ -vertex graph with the minimum degree $k+1$ contains a cycle of length at least $\min\{n, 2(k+1)\}$ . Here we obtain a stability version of this result by characterizing those graphs with minimum degree $k$ and circumference at most $2k+1$ . We present applications of the above-stated result by obtaining generalized Turán numbers. In particular, for all $\ell \geq 5$ we determine how many copies of a five-cycle as well as four-cycle are necessary to guarantee that the graph has circumference larger than $\ell$ . In addition, we give a new proof of Luo's Theorem for cliques using our stability result.

preprint2022arXiv

Subgraph densities in $K_r$ -free graphs

In this paper we disprove a conjecture of Lidický and Murphy about the number of copies of a given graph in a $K_r$ -free graph and give an alternative general conjecture. We also prove an asymptotically tight bound on the number of copies of any bipartite graph of radius at most $2$ in a triangle-free graph.

preprint2022arXiv

The maximum number of copies of an even cycle in a planar graph

We resolve a conjecture of Cox and Martin by determining asymptotically for every $k\ge 2$ the maximum number of copies of $C_{2k}$ in an $n$ -vertex planar graph.

preprint2022arXiv

The maximum number of triangles in $F_k$ -free graphs

The generalized Turán number $ex(n,K_s,H)$ is the maximum number of complete graph $K_s$ in an $H$ -free graph on $n$ vertices. Let $F_k$ be the friendship graph consisting of $k$ triangles. Erdős and Sós (1976) determined the value of $ex(n,K_3,F_2)$ . Alon and Shikhelman (2016) proved that $ex(n,K_3, F_k)\le (9k-15)(k+1)n.$ In this paper, by using a method developed by Chung and Frankl in hypergraph theory, we determine the exact value of $ex(n,K_3,F_k)$ and the extremal graph for any $F_k$ when $n\ge 4k^3$ .

preprint2021arXiv

Inverse Turán numbers

For given graphs $G$ and $F$ , the Turán number $ex(G,F)$ is defined to be the maximum number of edges in an $F$ -free subgraph of $G$ . Foucaud, Krivelevich and Perarnau and later independently Briggs and Cox introduced a dual version of this problem wherein for a given number $k$ , one maximizes the number of edges in a host graph $G$ for which $ex(G,H) < k$ . Addressing a problem of Briggs and Cox, we determine the asymptotic value of the inverse Turán number of the paths of length $4$ and $5$ and provide an improved lower bound for all paths of even length. Moreover, we obtain bounds on the inverse Turán number of even cycles giving improved bounds on the leading coefficient in the case of $C_4$ . Finally, we give multiple conjectures concerning the asymptotic value of the inverse Turán number of $C_4$ and $P_{\ell}$ , suggesting that in the latter problem the asymptotic behavior depends heavily on the parity of $\ell$ .

preprint2020arXiv

Edge colorings of graphs without monochromatic stars

In this note, we improve on results of Hoppen, Kohayakawa and Lefmann about the maximum number of edge colorings without monochromatic copies of a star of a fixed size that a graph on $n$ vertices may admit. Our results rely on an improved application of an entropy inequality of Shearer.

preprint2020arXiv

Generalized Planar Turán Numbers

In a generalized Turán problem, we are given graphs $H$ and $F$ and seek to maximize the number of copies of $H$ in an $F$ -free graph of order $n$ . We consider generalized Turán problems where the host graph is planar. In particular we obtain the order of magnitude of the maximum number of copies of a fixed tree in a planar graph containing no even cycle of length at most $2\ell$ , for all $\ell$ , $\ell \geq 1$ . We obtain the order of magnitude of the maximum number of cycles of a given length in a planar $C_4$ -free graph. An exact result is given for the maximum number of $5$ -cycles in a $C_4$ -free planar graph. Multiple conjectures are also introduced.

preprint2020arXiv

On $3$ -uniform hypergraphs avoiding a cycle of length four

In this note we show that the maximum number of edges in a $3$ -uniform hypergraph without a Berge cycle of length four is at most $(1+o(1))\frac{n^{3/2}}{\sqrt{10}}$ . This improves earlier estimates by Győri and Lemons and by Füredi and Özkahya.

preprint2020arXiv

On L(2,1)-labelings of some products of oriented cycles

We refine two results of Jiang, Shao and Vesel on the $L(2,1)$ -labeling number $λ$ of the Cartesian and the strong product of two oriented cycles. For the Cartesian product, we compute the exact value of $λ(\overrightarrow{C_m} \square \overrightarrow{C_n})$ for $m$ , $n \geq 40$ ; in the case of strong product, we either compute the exact value or establish a gap of size one for $λ(\overrightarrow{C_m} \boxtimes \overrightarrow{C_n})$ for $m$ , $n \geq 48$ .

preprint2020arXiv

Optimal pebbling number of the square grid

A pebbling move on a graph removes two pebbles from a vertex and adds one pebble to an adjacent vertex. A vertex is reachable from a pebble distribution if it is possible to move a pebble to that vertex using pebbling moves. The optimal pebbling number $π_{opt}$ is the smallest number m needed to guarantee a pebble distribution of m pebbles from which any vertex is reachable. The optimal pebbling number of the square grid graph $P_n\square P_m$ was investigated in several papers. In this paper, we present a new method using some recent ideas to give a lower bound on $π_{opt}$ . We apply this technique to prove that $π_{opt}(P_n\square P_m)\geq \frac{2}{13}nm$ . Our method also gives a new proof for $π_{opt}(P_n)=π_{opt}(C_n)=\left\lceil\frac{2n}{3}\right\rceil$ .

preprint2020arXiv

Planar Turán number of the 6-cycle

Let ${\rm ex}_{\mathcal{P}}(n,T,H)$ denote the maximum number of copies of $T$ in an $n$ -vertex planar graph which does not contain $H$ as a subgraph. When $T=K_2$ , ${\rm ex}_{\mathcal{P}}(n,T,H)$ is the well studied function, the planar Turán number of $H$ , denoted by ${\rm ex}_{\mathcal{P}}(n,H)$ . The topic of extremal planar graphs was initiated by Dowden (2016). He obtained sharp upper bound for both ${\rm ex}_{\mathcal{P}}(n,C_4)$ and ${\rm ex}_{\mathcal{P}}(n,C_5)$ . Later on, Y. Lan, et al. continued this topic and proved that ${\rm ex}_{\mathcal{P}}(n,C_6)\leq \frac{18(n-2)}{7}$ . In this paper, we give a sharp upper bound ${\rm ex}_{\mathcal{P}}(n,C_6) \leq \frac{5}{2}n-7$ , for all $n\geq 18$ , which improves Lan's result. We also pose a conjecture on ${\rm ex}_{\mathcal{P}}(n,C_k)$ , for $k\geq 7$ .

preprint2020arXiv

The anti-Ramsey number of $C_{3}$ and $C_{4}$ in the complete $r$ -partite graphs

A subgraph of an edge-colored graph is rainbow, if all of its edges have different colors. For a graph $G$ and a family $\mathcal{H}$ of graphs, the anti-Ramsey number $ar(G, \mathcal{H})$ is the maximum number $k$ such that there exists an edge-coloring of $G$ with exactly $k$ colors without rainbow copy of any graph in $\mathcal{H}$ . In this paper, we study the anti-Ramsey number of $C_{3}$ and $C_{4}$ in the complete $r$ -partite graphs. For $r\ge 3$ and $n_{1}\ge n_{2}\ge \cdots\ge n_{r}\ge 1$ , we determine $ar(K_{n_{1}, n_{2}, \ldots, n_{r}},\{C_{3}, C_{4}\}), ar(K_{n_{1}, n_{2}, \ldots, n_{r}}, C_{3})$ and $ar(K_{n_{1}, n_{2}, \ldots, n_{r}}, C_{4})$ .

preprint2020arXiv

The exact linear Turán number of the Sail

A hypergraph is linear if any two of its edges intersect in at most one vertex. The Sail (or $3$ -fan) $F^3$ is the $3$ -uniform linear hypergraph consisting of $3$ edges $f_1, f_2, f_3$ pairwise intersecting in the same vertex $v$ and an additional edge $g$ intersecting all $f_i$ in a vertex different from $v$ . The linear Turán number $ex_{lin}(n, F^3)$ is the maximum number of edges in a $3$ -uniform linear hypergraph on $n$ vertices that does not contain a copy of $F^3$ . Füredi and Gyárfás proved that if $n = 3k$ , then $ex_{lin}(n, F^3) = k^2$ and the only extremal hypergraphs in this case are transversal designs. They also showed that if $n = 3k+2$ , then $ex_{lin}(n, F^3) = k^2+k$ , and the only extremal hypergraphs are truncated designs (which are obtained from a transversal design on $3k+3$ vertices with $3$ groups by removing one vertex and all the hyperedges containing it) along with three other small hypergraphs. However, the case when $n =3k+1$ was left open. In this paper, we solve this remaining case by proving that $ex_{lin}(n, F^3) = k^2+1$ if $n = 3k+1$ , answering a question of Füredi and Gyárfás. We also characterize all the extremal hypergraphs. The difficulty of this case is due to the fact that these extremal examples are rather non-standard. In particular, they are not derived from transversal designs like in the other cases.

preprint2020arXiv

Turán numbers of Berge trees

A classical conjecture of Erdős and Sós asks to determine the Turán number of a tree. We consider variants of this problem in the settings of hypergraphs and multi-hypergraphs. In particular, for all $k$ and $r$ , with $r \ge k (k-2)$ , we show that any $r$ -uniform hypergraph $\mathcal{H}$ with more than $\frac{n(k-1)}{r+1}$ hyperedges contains a Berge copy of any tree with $k$ edges different from the $k$ -edge star. This bound is sharp when $r+1$ divides $n$ and for such values of $n$ we determine the extremal hypergraphs.

preprint2020arXiv

Wiener Index of Quadrangulation Graphs

The Wiener index of a graph $G$ , denoted $W(G)$ , is the sum of the distances between all pairs of vertices in $G$ . É. Czabarka, et al. conjectured that for an $n$ -vertex, $n\geq 4$ , simple quadrangulation graph $G$ , \begin{equation*}W(G)\leq \begin{cases} \frac{1}{12}n^3+\frac{7}{6}n-2, &\text{ $n\equiv 0~(mod \ 2)$ ,}\\ \frac{1}{12}n^3+\frac{11}{12}n-1, &\text{ $n\equiv 1~(mod \ 2)$ }. \end{cases} \end{equation*} In this paper, we confirm this conjecture.

preprint2019arXiv

On L(2,1)-labelings of oriented graphs

We extend a result of Griggs and Yeh about the maximum possible value of the L(2,1)-labeling number of a graph in terms of its maximum degree to oriented graphs. We consider the problem both in the usual definition of the oriented L(2,1)-labeling number and in some variants we introduce.

preprint2018arXiv

Terminal-Pairability in Complete Bipartite Graphs with Non-Bipartite Demands

We investigate the terminal-pairability problem in the case when the base graph is a complete bipartite graph, and the demand graph is a (not necessarily bipartite) multigraph on the same vertex set. In computer science, this problem is known as the edge-disjoint paths problem. We improve the lower bound on the maximum value of $Δ(D)$ which still guarantees that the demand graph $D$ has a realization in $K_{n,n}$ . We also solve the extremal problem on the number of edges, i.e., we determine the maximum number of edges which guarantees that a demand graph is realizable in $K_{n,n}$ .

preprint2017arXiv

Terminal-Pairability in Complete Bipartite Graphs

We investigate the terminal-pairibility problem in the case when the base graph is a complete bipartite graph, and the demand graph is also bipartite with the same color classes. We improve the lower bound on maximum value of $Δ(D)$ which still guarantees that the demand graph $D$ is terminal-pairable in this setting. We also prove a sharp theorem on the maximum number of edges such a demand graph can have.

preprint2016arXiv

Clique Coverings and Claw-free Graphs

Let $\cal C$ be a clique covering for $E(G)$ and let $v$ be a vertex of $G$ . The valency of vertex $v$ (with respect to $\cal C$ ), denoted by $val_{\cal C}(v)$ , is the number of cliques in $\cal C$ containing $v$ . The local clique cover number of $G$ , denoted by $lcc(G)$ , is defined as the smallest integer $k$ , for which there exists a clique covering for $E(G)$ such that $val_{\cal C}(v)$ is at most $k$ , for every vertex $v\in V(G)$ . In this paper, among other results, we prove that if $G$ is a claw-free graph, then $lcc(G)+χ(G)\leq n+1$ .

preprint2016arXiv

On the Linear Cycle Cover Conjecture of Gyárfás and Sárközy

A linear cycle in a hypergraph $H$ is a cyclic sequence of hyperedges such that two consecutive hyperedges intersect in exactly one element and two nonconsecutive hyperedges are disjoint and $α(H)$ denotes the size of a largest independent set of $H$ . In this note, we show that the vertex set of every $3$ -uniform hypergraph $H$ can be covered by at most $α(H)$ pairwise edge-disjoint linear cycles (where we accept a vertex and a hyperedge as a linear cycle), proving a weaker version of a conjecture of Gyárfás and Sárközy.

preprint2016arXiv

The Optimal Pebbling Number of Staircase Graphs

Let G be a graph with a distribution of pebbles on its vertices. A pebbling move consists of removing two pebbles from one vertex and placing one pebble on an adjacent vertex. The optimal pebbling number of G is the smallest number of pebbles which can placed on the vertices of G such that, for any vertex v of G, there is a sequence of pebbling moves resulting in at least one pebble on v. We determine the optimal pebbling number for several classes of induced subgraphs of the square grid, which we call staircase graphs.

preprint2015arXiv

A list version of graph packing

We consider the following generalization of graph packing. Let $G_{1} = (V_{1}, E_{1})$ and $G_{2} = (V_{2}, E_{2})$ be graphs of order $n$ and $G_{3} = (V_{1} \cup V_{2}, E_{3})$ a bipartite graph. A bijection $f$ from $V_{1}$ onto $V_{2}$ is a list packing of the triple $(G_{1}, G_{2}, G_{3})$ if $uv \in E_{2}$ implies $f(u)f(v) \notin E_{2}$ and $vf(v) \notin E_{3}$ for all $v \in V_{1}$ . We extend the classical results of Sauer and Spencer and Bollobás and Eldridge on packing of graphs with small sizes or maximum degrees to the setting of list packing. In particular, we extend the well-known Bollobás--Eldridge Theorem, proving that if $Δ(G_{1}) \leq n-2, Δ(G_{2}) \leq n-2, Δ(G_{3}) \leq n-1$ , and $|E_1| + |E_2| + |E_3| \leq 2n-3$ , then either $(G_{1}, G_{2}, G_{3})$ packs or is one of 7 possible exceptions. Hopefully, the concept of list packing will help to solve some problems on ordinary graph packing, as the concept of list coloring did for ordinary coloring.

preprint2015arXiv

On the number of edge-disjoint triangles in $K_4$ -free graphs

We show the quarter of a century old conjecture that every $K_4$ -free graph with $n$ vertices and $\lfloor n^2/4 \rfloor +k$ edges contains $k$ pairwise edge disjoint triangles.

preprint2015arXiv

Toward Żak's conjecture on graph packing

Two graphs $G_{1} = (V_{1}, E_{1})$ and $G_{2} = (V_{2}, E_{2})$ , each of order $n$ , pack if there exists a bijection $f$ from $V_{1}$ onto $V_{2}$ such that $uv \in E_{1}$ implies $f(u)f(v) \notin E_{2}$ . In 2014, Żak proved that if $Δ(G_{1}), Δ(G_{2}) \leq n-2$ and $|E_{1}| + |E_{2}| + \max \{ Δ(G_{1}), Δ(G_{2}) \} \leq 3n - 96n^{3/4} - 65$ , then $G_{1}$ and $G_{2}$ pack. In the same paper, he conjectured that if $Δ(G_{1}), Δ(G_{2}) \leq n-2$ , then $|E_{1}| + |E_{2}| + \max \{ Δ(G_{1}), Δ(G_{2}) \} \leq 3n - 7$ is sufficient for $G_{1}$ and $G_{2}$ to pack. We prove that, up to an additive constant, Żak's conjecture is correct. Namely, there is a constant $C$ such that if $Δ(G_1),Δ(G_2) \leq n-2$ and $|E_{1}| + |E_{2}| + \max \{ Δ(G_{1}), Δ(G_{2}) \} \leq 3n - C$ , then $G_{1}$ and $G_{2}$ pack. In order to facilitate induction, we prove a stronger result on list packing.

preprint2014arXiv

On $3$ -uniform hypergraphs without linear cycles

We explore properties of $3$ -uniform hypergraphs $H$ without linear cycles. Our main results are that these hypergraphs must contain a vertex of strong degree at most two and must have independent sets of size at least ${2|V(H)|\over 5}$ .

Ervin Győri

Research overview

Is this your work?

29 publications

The maximum number of triangles in graphs without the square of a path

Exact results for generalized extremal problems forbidding an even cycle

Extremal planar graphs with no cycles of particular lengths

Planar Turán Number of Double Stars

Stability version of Dirac's theorem and its applications for generalized Turán problems

Subgraph densities in $K_r$ -free graphs

The maximum number of copies of an even cycle in a planar graph

The maximum number of triangles in $F_k$ -free graphs

Inverse Turán numbers

Edge colorings of graphs without monochromatic stars

Generalized Planar Turán Numbers

On $3$ -uniform hypergraphs avoiding a cycle of length four

On L(2,1)-labelings of some products of oriented cycles

Optimal pebbling number of the square grid

Planar Turán number of the 6-cycle

The anti-Ramsey number of $C_{3}$ and $C_{4}$ in the complete $r$ -partite graphs

The exact linear Turán number of the Sail

Turán numbers of Berge trees

Wiener Index of Quadrangulation Graphs

On L(2,1)-labelings of oriented graphs

Terminal-Pairability in Complete Bipartite Graphs with Non-Bipartite Demands

Terminal-Pairability in Complete Bipartite Graphs

Clique Coverings and Claw-free Graphs

On the Linear Cycle Cover Conjecture of Gyárfás and Sárközy

The Optimal Pebbling Number of Staircase Graphs

A list version of graph packing

On the number of edge-disjoint triangles in $K_4$ -free graphs

Toward Żak's conjecture on graph packing

On $3$ -uniform hypergraphs without linear cycles

See the researcher in context

Building this map preview

Ervin Győri

Research overview

Is this your work?

29 publications

The maximum number of triangles in graphs without the square of a path

Exact results for generalized extremal problems forbidding an even cycle

Extremal planar graphs with no cycles of particular lengths

Planar Turán Number of Double Stars

Stability version of Dirac's theorem and its applications for generalized Turán problems

Subgraph densities in KrK_rKr​-free graphs

The maximum number of copies of an even cycle in a planar graph

The maximum number of triangles in FkF_kFk​-free graphs

Inverse Turán numbers

Edge colorings of graphs without monochromatic stars

Generalized Planar Turán Numbers

On 333-uniform hypergraphs avoiding a cycle of length four

On L(2,1)-labelings of some products of oriented cycles

Optimal pebbling number of the square grid

Planar Turán number of the 6-cycle

The anti-Ramsey number of C3C_{3}C3​ and C4C_{4}C4​ in the complete rrr-partite graphs

The exact linear Turán number of the Sail

Turán numbers of Berge trees

Wiener Index of Quadrangulation Graphs

On L(2,1)-labelings of oriented graphs

Terminal-Pairability in Complete Bipartite Graphs with Non-Bipartite Demands

Terminal-Pairability in Complete Bipartite Graphs

Clique Coverings and Claw-free Graphs

On the Linear Cycle Cover Conjecture of Gyárfás and Sárközy

The Optimal Pebbling Number of Staircase Graphs

A list version of graph packing

On the number of edge-disjoint triangles in K4K_4K4​-free graphs

Toward Żak's conjecture on graph packing

On 333-uniform hypergraphs without linear cycles

See the researcher in context

Building this map preview

Subgraph densities in $K_r$ -free graphs

The maximum number of triangles in $F_k$ -free graphs

On $3$ -uniform hypergraphs avoiding a cycle of length four

The anti-Ramsey number of $C_{3}$ and $C_{4}$ in the complete $r$ -partite graphs

On the number of edge-disjoint triangles in $K_4$ -free graphs

On $3$ -uniform hypergraphs without linear cycles