The Library
Dense H-free graphs are almost (Χ(H)-1)-partite
Tools
Allen, Peter (2010) Dense H-free graphs are almost (Χ(H)-1)-partite. Electronic Journal of Combinatorics, Vol.17 (No.1:R21). ISSN 1097-1440.
PDF
WRAP_Allen_Dense_h-Free_Graphs.pdf - Requires a PDF viewer. Download (199Kb) |
Official URL: http://www.combinatorics.org/index.html
Abstract
By using the Szemeredi Regularity Lemma, Alon and Sudakov recently
extended the classical Andrasfai-Erdos-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, there exists
a constant C such that for any given ε>0 and sufficiently large n the following is
true. Whenever G is an n-vertex graph with minimum degree
δ(G)≥(1 −
3/3r−1 + ε)n,
either G contains H, or we can delete f(n,H)≤Cn2−1/t edges from G to obtain an
r-partite graph. Further, we are able to determine the correct order of magnitude
of f(n,H) in terms of the Zarankiewicz extremal function.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Library of Congress Subject Headings (LCSH): | Graph theory | ||||
Journal or Publication Title: | Electronic Journal of Combinatorics | ||||
Publisher: | Electronic Journal of Combinatorics | ||||
ISSN: | 1097-1440 | ||||
Official Date: | 29 January 2010 | ||||
Dates: |
|
||||
Volume: | Vol.17 | ||||
Number: | No.1:R21 | ||||
Status: | Peer Reviewed | ||||
Access rights to Published version: | Open Access (Creative Commons) | ||||
Funder: | Engineering and Physical Sciences Research Council (EPSRC) | ||||
Grant number: | EP/D063191/1 (EPSRC) |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year