Unavoidable subgraphs of colored graphs Original Research Article

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 image be the family of two-edge-colored graphs on k vertices such that one of the colors forms either two disjoint imageʹs or simply one image. Bollobás conjectured that for all k and image, there exists an image such that if image then every two-edge-coloring of image, in which the density of each color is at least image, contains a member of this family. We solve this conjecture and present a series of results bounding image for different ranges of image. In particular, if image is sufficiently close to image, the gap between our upper and lower bounds for image is smaller than those for the classical Ramsey number image.