ﻻ يوجد ملخص باللغة العربية
Generalized Turan problems have been a central topic of study in extremal combinatorics throughout the last few decades. One such problem is maximizing the number of cliques of size $t$ in a graph of a fixed order that does not contain any path (or cycle) of length at least a given number. Both of the path-free and cycle-free extremal problems were recently considered and asymptotically solved by Luo. We fully resolve these problems by characterizing all possible extremal graphs. We further extend these results by solving the edge-variant of these problems where the number of edges is fixed instead of the number of vertices. We similarly obtain exact characterization of the extremal graphs for these edge variants.
The triangle covering number of a graph is the minimum number of vertices that hit all triangles. Given positive integers $s,t$ and an $n$-vertex graph $G$ with $lfloor n^2/4 rfloor +t$ edges and triangle covering number $s$, we determine (for large
Extending the concept of Ramsey numbers, Erd{H o}s and Rogers introduced the following function. For given integers $2le s<t$ let $$ f_{s,t}(n)=min {max {|W| : Wsubseteq V(G) {and} G[W] {contains no} K_s} }, $$ where the minimum is taken over all $K_
For fixed $p$ and $q$, an edge-coloring of the complete graph $K_n$ is said to be a $(p, q)$-coloring if every $K_p$ receives at least $q$ distinct colors. The function $f(n, p, q)$ is the minimum number of colors needed for $K_n$ to have a $(p, q)$-
For a 2-connected graph $G$ on $n$ vertices and two vertices $x,yin V(G)$, we prove that there is an $(x,y)$-path of length at least $k$ if there are at least $frac{n-1}{2}$ vertices in $V(G)backslash {x,y}$ of degree at least $k$. This strengthens a
Let $textbf{k} := (k_1,ldots,k_s)$ be a sequence of natural numbers. For a graph $G$, let $F(G;textbf{k})$ denote the number of colourings of the edges of $G$ with colours $1,dots,s$ such that, for every $c in {1,dots,s}$, the edges of colour $c$ con