We have 6 of 10 papers
We haven’t gathered this author’s papers yet. Follow them and we’ll fetch their work.
Not the right person? Other researchers publish under this name.
For a graph $G$, let $\nu(G)$ denote the maximum number of pairwise edge-disjoint triangles and let $\tau(G)$ denote the minimum number of edges meeting every triangle. Tuza's conjecture asserts that $\tau(G)\le 2\nu(G)$ for every graph $G$. We first note that Tuza's conjecture is equivalent to the following statement:...
For graphs $H$ and $F$, let $\text{ex}(n,H,F)$ denote the maximum number of copies of $H$ in an $n$-vertex $F$-free graph. Gerbner, Gy\H{o}ri, Methuku, and Vizer proved that $\text{ex}(n,C_{2\ell},C_{2k})=\Theta(n^\ell)$ for $k>\ell\ge2$. They determined the leading term for $\ell=2$, but for $k>\ell\ge3$ their general...
For a graph $G$, let $\alpha_1(G)$ be the maximum size of an edge set containing at most one edge from every triangle, and let $\tau_1(G)$ be the minimum size of an edge set meeting every triangle. Erd\H{o}s, Gallai, and Tuza proved that $\alpha_1(G)+\tau_1(G)=\Omega(m^{2/3})$ for every $m$-edge graph and asked for the...
We prove that, for every integer $k\ge 2$, there exists a constant $c_k>0$ such that every graph on $n\ge R(k,k)$ vertices with maximum degree $\Delta$ contains an induced subgraph on at least $n-c_k\sqrt{\Delta}$ vertices whose maximum degree is attained by at least $k$ vertices. This confirms a conjecture of Caro and...
For graphs $G$ and $H$, let $\mathbf N(G,H)$ denote the number of unlabeled, not necessarily induced copies of $H$ in $G$, and let $\mathbf N_{\mathcal P}(n,H)$ be the maximum of $\mathbf N(G,H)$ over all $n$-vertex planar graphs $G$. We prove that, for every fixed integer $m\geq 3$, $$\mathbf N_{\mathcal P}(n,C_{2m+1}...
For a graph $H$ and a family of graphs $\mathcal F$, let $\text{ex}(n,H,\mathcal F)$ denote the maximum number of copies of $H$ in an $\mathcal F$-free graph on $n$ vertices. For every integer $i\ge 3$, let $C_i$ denote the cycle of length $i$. For $r\ge 3$, set $\mathscr {C}_r=\{C_3,C_4,\ldots,C_r\},$ and set $\mathsc...
We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.
