umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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, p. 4396-4413Article in journal (Refereed) Published
Resource type
Text
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, p. 4396-4413
Keywords [en]
Ramsey theory, unavoidable structures
National Category
Discrete Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-117479DOI: 10.1016/j.disc.2007.08.102ISI: 000257978700011OAI: oai:DiVA.org:umu-117479DiVA, id: diva2:911396
Conference
Workshop on Extremal Graph Theory, JUN 23-27, 2003, Csopak, HUNGARY
Available from: 2016-03-11 Created: 2016-03-01 Last updated: 2018-03-15Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text
By organisation
Department of mathematics
In the same journal
Discrete Mathematics
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 52 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf