Show simple item record

dc.contributor.authorMubayi, Dhruv
dc.date.accessioned2011-02-28T16:54:54Z
dc.date.available2011-02-28T16:54:54Z
dc.date.issued2010-12-01
dc.identifier.bibliographicCitationMubayi, D. 2010. Counting substructures I: Color critical graphs. Advances in Mathematics, 225(5): 2731-2740. DOI: 10.1016/j.aim.2010.05.013en
dc.identifier.issn0001-8708
dc.identifier.otherDOI: 10.1016/j.aim.2010.05.013
dc.identifier.urihttp://hdl.handle.net/10027/7343
dc.descriptionPost print version of article may differ from published version. The definitive version is available through Elsevier at DOI: 10.1016/j.aim.2010.05.013en
dc.description.abstractLet F be a graph which contains an edge whose deletion reduces its chromatic number. We prove tight bounds on the number of copies of F in a graph with a prescribed number of vertices and edges. Our results extend those of Simonovits [8], who proved that there is one copy of F, and of Rademacher, Erdos [1, 2] and Lovasz- Simonovits [4], who proved similar counting results when F is a complete graph. One of the simplest cases of our theorem is the following new result. There is an absolute positive constant c such that if n is sufficiently large and 1 <= q < cn, then every n vertex graph with [n(2)/4] + q edges contains at least [equation] copies of a five cycle. Similar statements hold for any odd cycle and the bounds are best possible.en
dc.description.sponsorshipNational Science Foundation grant DMS-0969092en
dc.language.isoen_USen
dc.publisherElsevieren
dc.subjectextremal graph theoryen
dc.subjectstabilityen
dc.subjectremoval lemmaen
dc.titleCounting substructures I: Color critical graphsen
dc.typeArticleen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record