Dense H-free graphs are almost (χ(H)-1)-partite

Details Dense H-free graphs are almost (χ(H)-1)-partite Dense H-free graphs are almost (χ(H)-1)-partite

2009-07-22

arxiv.org/abs/0907.3815v3

Mathematics

Combinatorics

18 pages, no figures. Published in Electronic Journal of Combinatorics without appendix (added after publication) detailing wh

Scientific paper

By using the Szemer\'edi Regularity Lemma, Alon and Sudakov recently extended the classical Andr\'asfai-Erd\~os-S\'os 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.

Affiliated with

Also associated with

No associations

Rating

Dense H-free graphs are almost (χ(H)-1)-partite does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Dense H-free graphs are almost (χ(H)-1)-partite, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dense H-free graphs are almost (χ(H)-1)-partite will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-128124