Extending Ramsey Numbers for Connected Graphs of Size 3

Abstract

It is well known that the famous Ramsey number R(K3,K3)=6. That is, the minimum positive integer n for which every red-blue coloring of the edges of the complete graph Kn results in a monochromatic triangle K3 is 6. It is also known that every red-blue coloring of K6 results in at least two monochromatic triangles, which need not be vertex-disjoint or edge-disjoint. This fact led to an extension of Ramsey numbers. For a graph F and a positive integer t, the vertex-disjoint Ramsey number VRt(F) is the minimum positive integer n such that every red-blue coloring of the edges of the complete graph Kn of order n results in t pairwise vertex-disjoint monochromatic copies of subgraphs isomorphic to F, while the edge-disjoint Ramsey number ERt(F) is the corresponding number for edge-disjoint subgraphs. Since VR1(F) and ER1(F) are the well-known Ramsey numbers of F, these new Ramsey concepts generalize the Ramsey numbers and provide a new perspective for this classical topic in graph theory. These numbers have been investigated for the two connected graphs K3 and the path P3 of order 3. Here, we study these numbers for the remaining connected graphs, namely, the path P4 and the star K1,3 of size 3. We show that VRt(P4)=4t+1 for every positive integer t and VRt(K1,3)=4t for every integer t≥2. For t≤4, the numbers ERt(K1,3) and ERt(P4) are determined. These numbers provide information towards the goal of determining how the numbers VRt(F) and ERt(F) increase as t increases for each graph F∈{K1,3,P4}.

Keywords

• red-blue coloring
• edge-disjoint
• vertex-disjoint Ramsey numbers