INDIGO Home University of Illinois at Urbana-Champaign logo uic building uic pavilion uic student center

Counting substructures I: Color critical graphs

Show full item record

Bookmark or cite this item: http://hdl.handle.net/10027/7343

Files in this item

File Description Format
PDF graphcount-1.pdf (150KB) (no description provided) PDF
Title: Counting substructures I: Color critical graphs
Author(s): Mubayi, Dhruv
Subject(s): extremal graph theory stability removal lemma
Abstract: Let 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.
Issue Date: 2010-12-01
Publisher: Elsevier
Citation Info: Mubayi, D. 2010. Counting substructures I: Color critical graphs. Advances in Mathematics, 225(5): 2731-2740. DOI: 10.1016/j.aim.2010.05.013
Type: Article
Description: Post print version of article may differ from published version. The definitive version is available through Elsevier at DOI: 10.1016/j.aim.2010.05.013
URI: http://hdl.handle.net/10027/7343
ISSN: 0001-8708
Sponsor: National Science Foundation grant DMS-0969092
Date Available in INDIGO: 2011-02-28
 

This item appears in the following Collection(s)

Show full item record

Statistics

Country Code Views
United States of America 69
China 20
United Kingdom 8
Netherlands 3
Germany 1

Browse

My Account

Information

Access Key