DMTCS Proceedings, 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

Font Size:  Small  Medium  Large

Chromatic Turán problems and a new upper bound for the Turán density of K4-

John Talbot


We consider a new type of extremal hypergraph problem: given an r-graph F and an integer k≥2 determine the maximum number of edges in an F-free, k-colourable r-graph on n vertices. Our motivation for studying such problems is that it allows us to give a new upper bound for an old problem due to Turán. We show that a 3-graph in which any four vertices span at most two edges has density less than 33 / 100, improving previous bounds of 1 / 3 due to de Caen [deC], and 1 / 3-4.5305×10-6 due to Mubayi [M].

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page

Valid XHTML 1.0 Transitional