Name
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 S\"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 @e0, there exists an n(k,@e) such that if n=n(k,@e) then every two-edge-coloring of K\"n, in which the density of each color is at least @e, contains a member of this family. We solve this conjecture and present a series of results bounding n(k,@e) for different ranges of @e. In particular, if @e is sufficiently close to 12, the gap between our upper and lower bounds for n(k,@e) is smaller than those for the classical Ramsey number R(k,k). |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.disc.2007.08.102 | Discrete Mathematics |
Keywords | Field | DocType |
unavoidable structures,05c55,ramsey theory,edge coloring,upper and lower bounds,ramsey number | Graph theory,Integer,Ramsey theory,Discrete mathematics,Combinatorics,Disjoint sets,Vertex (geometry),Upper and lower bounds,Ramsey's theorem,Conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
308 | 19 | Discrete Mathematics |
Citations | PageRank | References |
3 | 0.51 | 3 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jonathan Cutler | 1 | 3 | 0.51 |
| Balázs Montágh | 2 | 3 | 0.51 |