Strong Ramsey Numbers of Graphs of Size 4
Abstract
The Ramsey number R(G) of a graph G without isolated vertices is the minimum order n of the complete graph Kn for which every red-blue edge coloring results in a monochromatic subgraph isomorphic to G. The strong Ramsey number R¯(F,H) of two non-isomorphic graphs F and H without isolated vertices is the minimum positive integer n such that every red-blue coloring of Kn results in two edge-disjoint monochromatic subgraphs, one isomorphic to F and the other isomorphic to H. The numbers R¯(F,H) have been determined for all pairs F,H of non-isomorphic graphs F and H of size 3. Here, R¯(F,H) is determined for all pairs F,H of non-isomorphic graphs F and H of size 4. In each case, it is shown that R¯(F,H) is either max{R(F),R(H)} or 1+max{R(F),R(H)}. Furthermore, R¯(F,H) has been determined for some special pairs F,H of non-isomorphic graphs.
Fields of Study & Subjects
Limits and Structures in Graph Theory
Advanced Graph Theory Research
Advanced Topology and Set Theory
Publication details
- Journal / source
- Mathematics
- Publisher
- MDPI AG
- Volume
- 14
- Issue
- 12
- Pages
- 2158–2158
- Publication date
- 16 June 2026
- Language
- EN