ﻻ يوجد ملخص باللغة العربية
By using the Szemeredi Regularity Lemma, Alon and Sudakov recently extended the classical Andrasfai-Erd~os-Sos theorem to cover general graphs. We prove, without using the Regularity Lemma, that the following stronger statement is true. Given any (r-1)-partite graph H whose smallest part has t vertices, and any fixed c>0, there exists a constant C such that whenever G is an n-vertex graph with minimum degree at least ((3r-4)/(3r-1)+c)n, either G contains H, or we can delete at most Cn^(2-1/t) edges from G to yield an r-partite graph.
Given a graph $H$, a graph is $H$-free if it does not contain $H$ as a subgraph. We continue to study the topic of extremal planar graphs, that is, how many edges can an $H$-free planar graph on $n$ vertices have? We define $ex_{_mathcal{P}}(n,H)$ to
The ErdH{o}s-Simonovits stability theorem states that for all epsilon >0 there exists alpha >0 such that if G is a K_{r+1}-free graph on n vertices with e(G) > ex(n,K_{r+1}) - alpha n^2, then one can remove epsilon n^2 edges from G to obtain an r-par
A graph $G$ is total weight $(k,k)$-choosable if for any total list assignment $L$ which assigns to each vertex $v$ a set $L(v)$ of $k$ real numbers, and each edge $e$ a set $L(e)$ of $k$ real numbers, there is a proper total $L$-weighting, i.e., a m
The well-known Disjoint Paths problem is to decide if a graph contains k pairwise disjoint paths, each connecting a different terminal pair from a set of k distinct pairs. We determine, with an exception of two cases, the complexity of the Disjoint P
A grounded L-graph is the intersection graph of a collection of L shapes whose topmost points belong to a common horizontal line. We prove that every grounded L-graph with clique number $omega$ has chromatic number at most $17omega^4$. This improves