Article ID Journal Published Year Pages File Type
4647392 Discrete Mathematics 2013 12 Pages PDF
Abstract

We say that a graph GG has the Ramsey property w.r.t. some graph FF and some integer r≥2r≥2, or GG is (F,r)(F,r)-Ramsey for short, if any rr-coloring of the edges of GG contains a monochromatic copy of FF. Rödl and Ruciński asked how globally sparse (F,r)(F,r)-Ramsey graphs GG can possibly be, where the density of GG is measured by the subgraph H⊆GH⊆G with the highest average degree. So far, this so-called Ramsey density is known only for cliques and some trivial graphs FF. In this work we determine the Ramsey density up to some small error terms for several cases when FF is a complete bipartite graph, a cycle or a path, and r≥2r≥2 colors are available.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,