Unavoidable subgraphs of colored graphs |
| |
Authors: | Jonathan Cutler Balázs Montágh |
| |
Institution: | a Department of Mathematical Sciences, University of Memphis, Memphis, TN 38152, USA b Matematiska institutionen, Umeå universitet, 901 87 Umeå, Sweden |
| |
Abstract: | 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 Sk be the family of two-edge-colored graphs on k vertices such that one of the colors forms either two disjoint Kk/2's or simply one Kk/2. Bollobás conjectured that for all k and ε>0, there exists an n(k,ε) such that if n?n(k,ε) then every two-edge-coloring of Kn, in which the density of each color is at least ε, contains a member of this family. We solve this conjecture and present a series of results bounding n(k,ε) for different ranges of ε. In particular, if ε is sufficiently close to , the gap between our upper and lower bounds for n(k,ε) is smaller than those for the classical Ramsey number R(k,k). |
| |
Keywords: | 05C55 |
本文献已被 ScienceDirect 等数据库收录! |
|