Strong Ramsey Numbers of All Sets of Three Graphs of Size 3

Abstract

The strong Ramsey number R¯(F,H) of two graphs F and H without isolated vertices is the minimum positive integer n such that every red-blue (edge) coloring of Kn results in two edge-disjoint monochromatic subgraphs, one isomorphic to F and the other isomorphic to H. These numbers have been determined for all such pairs F,H of graphs of size 3. For a set S of k≥2 graphs without isolated vertices, the strong Ramsey number R¯(S) of S is the minimum positive integer n such that every red-blue coloring of Kn results in k pairwise edge-disjoint monochromatic subgraphs isomorphic to the graphs in S. The number R¯(S) is determined for all sets of three graphs of size 3. Other results and questions on strong Ramsey numbers are also presented.