Change search
ReferencesLink to record
Permanent link

Direct link
Unavoidable subgraphs of colored graphs
Umeå University, Faculty of Science and Technology, Department of mathematics. Department of Mathematical Sciences, University of Memphis, Memphis, TN 38152, USA.
2008 (English)In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 308, no 19, 4396-4413 p.Article in journal (Refereed) PublishedText
Abstract [en]

A natural generalization of graph Ramsey theory is the study of unavoidable sub-graphs in large colored graphs. In this paper. we find a minimal family of unavoidable graphs in two-edge-colored graphs. Namely, for a positive even integer k, let y(k) be the family of two-edge-colored graphs on k vertices such that one of the colors forms either two disjoint K-k/2's or simply one K-k/2. Bollobas conjectured that for all k and epsilon > 0, there exists an n(k, epsilon) such that if n >= n(k, epsilon) then every two-edge-coloring of K-n, in which the density of each color is at least epsilon, contains a member of this family. We solve this conjecture and present a series of results bounding it (k, s) for different ranges of epsilon. In particular, if epsilon is sufficiently close to 1/2, the gap between out upper and lower bounds for n(k, epsilon) is smaller than those for the classical Ramsey number R(k, k).

Place, publisher, year, edition, pages
Amsterdam: Elsevier, 2008. Vol. 308, no 19, 4396-4413 p.
Keyword [en]
Ramsey theory, unavoidable structures
National Category
Discrete Mathematics
URN: urn:nbn:se:umu:diva-117479DOI: 10.1016/j.disc.2007.08.102ISI: 000257978700011OAI: diva2:911396
Workshop on Extremal Graph Theory, JUN 23-27, 2003, Csopak, HUNGARY
Available from: 2016-03-11 Created: 2016-03-01 Last updated: 2016-03-11Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Cutler, Jonathan
By organisation
Department of mathematics
In the same journal
Discrete Mathematics
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 15 hits
ReferencesLink to record
Permanent link

Direct link