Leírás
We call a graph G on n vertices (\alpha,k)-extremal if there
exists a vertex set A of size n/k, such that G(A) (the graph
induced by A) has density at most \alpha. One example is
the k-partite Turan graph.
Turan graphs or graphs close to the Turan graphs are very often
the extremal graphs for natural questions. So if we deal with
non-extremal graphs, in some cases, we expect stronger extremal
results that we generally have. One example when this happens is
the Erdos-Stone-Simonovits theorem.
We present two lemmas on non-extremal graphs. The first guarantees
the almost complete vertex covering of a non-(\alpha,k)-extremal
graph with ``large'' balanced complete k+1- and k-partite graphs
assuming that the minimal degree is large.
We also sketch how these lemmas imply the existence of k^th
power of a Hamiltonian cycle in a non-(\alpha,k)-extremal graph
with a relaxed degree condition compared to the Seymour conjecture.
Joint work with Endre Szemeredi