Pikhurko, Oleg and Yilma, Zelealem B. (2017) Supersaturation problem for color-critical graphs. Journal of Combinatorial Theory, Series B, 123 . pp. 148-185. doi:10.1016/j.jctb.2016.12.001 ISSN 0095-8956.

Preview	PDF WRAP_1-s2.0-S0095895616301083-main.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (1062Kb) | Preview
	PDF SuperSat2016a.pdf - Accepted Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (591Kb)

Request Changes to record.

Abstract

The Turán function ex(n, F) of a graph F is the maximum number of edges in an F-free graph with n vertices. The classical results of Turán and Rademacher from 1941 led to the study of supersaturated graphs where the key question is to determine hF (n, q), the minimum number of copies of F that a graph with n vertices and ex(n, F) + q edges can have. We determine hF (n, q) asymptotically when F is color-critical (that is, F contains an edge whose deletion reduces its chromatic number) and q = o(n 2 ). Determining the exact value of hF (n, q) seems rather difficult. For example, let c1 be the limit superior of q/n for which the extremal structures are obtained by adding some q edges to a maximum F-free graph. The problem of determining c1 for cliques was a well-known question of Erdős that was solved only decades later by Lovász and Simonovits. Here we prove that c1 > 0 for every color-critical F. Our approach also allows us to determine c1 for a number of graphs, including odd cycles, cliques with one edge removed, and complete bipartite graphs plus an edge.

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., Extremal problems (Mathematics)
Journal or Publication Title:	Journal of Combinatorial Theory, Series B
Publisher:	Academic Press
ISSN:	0095-8956
Official Date:	March 2017
Dates:	Date Event March 2017 Published 21 December 2016 Available 3 October 2016 Accepted
Volume:	123
Page Range:	pp. 148-185
DOI:	10.1016/j.jctb.2016.12.001
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Open Access (Creative Commons)
Date of first compliant deposit:	8 November 2016
Date of first compliant Open Access:	31 March 2017
Related URLs:	Publisher

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads