The Ramsey number \(R(G)\) of a graph \(G\) without isolated vertices is the minimum positive integer \(n\) such that for every red-blue coloring of the complete graph \(K_n\) of order \(n\), there is a subgraph isomorphic to \(G\) all of whose edges are colored the same (a monochromatic \(G\)). A Ramsey chain in a graph \(G\) with a red-blue coloring is a sequence \(G_1\), \(G_2\), \(\ldots\), \(G_{k}\) of pairwise edge-disjoint monochromatic subgraphs of \(G\) such that \(G_i\) has \(i\) edges for \(1 \le i \le k\) and \(G_i\) is isomorphic to a subgraph of \(G_{i+1}\) for \(1 \le i \le k-1\). The subgraphs in a Ramsey chain are the links of the chain and the terminal subgraph \(G_k\) is the target link of the chain. A graph \(H\) without isolated vertices is called a target graph if there exists a positive integer \(n\) such that every red-blue coloring of \(K_n\) results in a Ramsey chain with target link \(H\). The target Ramsey number \(TR(H)\) of \(H\) is the minimum positive integer \(n\) such that every red-blue coloring of \(K_n\) results in a Ramsey chain with target link \(H\). The target Ramsey number \(TR(s)\) of a Ramsey chain \(s\) is the minimum positive integer \(n\) such that \(s\) is a Ramsey chain in every red-blue coloring of \(K_{n}\). We investigate graphs \(H\) with the property that \(TR(s) =TR(H)= R(H)\) for every Ramsey chain \(s\) with target link \(H\). It is shown that every graph \(H\) with relatively small size has this property. Other results and open questions are also presented.
In a red-blue coloring of a graph \(G\), every edge of \(G\) is colored red or blue. For two graphs \(F\) and \(H\) (without isolated vertices), the Ramsey number \(R(F, H)\) of \(F\) and \(H\) is the minimum positive integer \(n\) such that for every red-blue coloring of the complete graph \(K_n\) of order \(n\), there is either a subgraph of \(K_n\) isomorphic to \(F\) all of whose edges are colored red (a red \(F\)) or a subgraph of \(K_n\) isomorphic to \(H\) all of whose edges are colored blue (a blue \(H\)). It is a consequence of a theorem of Ramsey [18] that the number \(R(F, H)\) exists for every two graphs \(F\) and \(H\). If \(F \cong H\), then the (diagonal) Ramsey number \(R(F, H)= R(H, H)= R(H)\) is the minimum positive integer \(n\) such that every red-blue coloring of \(K_n\) results in a subgraph of \(K_n\) isomorphic to \(F\) all of whose edges are colored the same (a monochromatic \(F\)).
A Ramsey chain in a graph \(G\) with a red-blue coloring is a sequence \(G_1\), \(G_2\), \(\ldots\), \(G_{k}\) of pairwise edge-disjoint subgraphs of \(G\) such that each subgraph \(G_i\) (\(1 \le i \le k\)) is monochromatic of size \(i\) and \(G_i\) is isomorphic to a subgraph of \(G_{i+1}\) for \(1 \le i \le k-1\). This concept was first introduced and studied in [2, 7]. The subgraphs in a Ramsey chain are the links of the chain and the terminal subgraph \(G_k\) of size \(k\) is the target link of the chain. A graph \(H\) without isolated vertices is called a target graph if there exists a positive integer \(n\) such that every red-blue coloring of \(K_n\) results in a Ramsey chain with target link \(H\). It was shown in [9] that every graph without isolated vertices is a target graph. For a target graph \(H\), the target Ramsey number \(TR(H)\) of \(H\) is the minimum positive integer \(n\) such that for every red-blue coloring of \(K_n\), there exists a Ramsey chain in \(K_n\) having \(H\) as its target link. In [9], it was shown that \(TR(H)\) exists for every graph \(H\) without isolated vertices and \(TR(H)\ge R(H)\). For every graph \(H\) that has been studied, it has been shown that \(TR(H)= R(H)\), which gave rise to the following question that appeared in [9, 8].
Question 1.1. Is there a graph \(H\) such that \(TR(H) > R(H)\)?
If the answer to this question is no, then \(TR(H) = R(H)\) for every graph \(H\). Hence, not only does every red-blue coloring of the complete graph \(K_{R(H)}\) of order \(R(H)\) produce a monochromatic \(H\) but also \(K_{R(H)}\) contains a Ramsey chain with target link \(H\). This implies that there are greater expectations for diagonal Ramsey numbers of graphs. Here, we introduce a related Ramsey concept and explore the possibility that the diagonal Ramsey number \(R(H)\) of a graph \(H\) may have a property that is stronger than \(TR(H) = R(H)\).
A sequence \(s=(G_1, G_2, \ldots, G_{k})\) of pairwise edge-disjoint graphs without isolated vertices is called an ascending sequence if \(G_i\) has size \(i\) for \(1\le i \le k\) and \(G_i\) is a subgraph of \(G_{i+1}\) for \(1 \le i \le k-1\). This concept is related to the Ascending Subgraph Decomposition Conjecture (see [1, 14]). An ascending sequence \(s\) is a Ramsey chain if there is a positive integer \(n\) such that \(s\) is a Ramsey chain in every red-blue coloring of \(K_n\).
Proposition 1.2. For every ascending sequence \(s\), there is a positive integer \(n\) such that \(s\) is a Ramsey chain in every red-blue coloring of \(K_n\); that is, every ascending sequence is a Ramsey chain.
Proof. Let \(s=(G_1, G_2, \ldots, G_k)\) be an ascending sequence. For \(1 \le i \le k\), let \(R(G_i) = n_i\) and let \(n =\sum_{i=1}^k n_i\). Let there be given a red-blue coloring of \(K_n\). Since \(n \ge n_k\), there is a monochromatic subgraph \(G_k\) in \(K_n\). Deleting the \(n_k\) vertices of \(G_k\) from \(K_n\) results in \(K_{n-n_k}\). Since \(n-n_k \ge n_{k-1}\) and \(E(K_{n-n_k}) \cap E(G_k) = \emptyset\), there is a monochromatic subgraph \(G_{k-1}\) in \(K_{n-n_k}\) that is edge-disjoint from \(G_k\). Continuing in this manner, we obtain a Ramsey chain \((G_1, G_2, \ldots, G_k)\) and so \(s\) is a Ramsey chain. \(\square\)
The target Ramsey number \(TR(s)\) of a Ramsey chain \(s\) is the minimum positive integer \(n\) such that \(s\) is a Ramsey chain in every red-blue coloring of \(K_{n}\). The following is a consequence of Proposition 1.2.
Observation 1.3. For every Ramsey chain \(s\), the target Ramsey number \(TR(s)\) exists. Furthermore, if the target link of \(s\) is \(H\), then \(TR(s) \ge TR(H)\ge R(H)\).
We now investigate the following question:
Which graphs \(H\) have the property that for every red-blue coloring of the complete graph \(K_{R(H)}\) of order \(R(H)\) and every Ramsey chain \(s\) with target link \(H\), it follows that \(TR(s) = R(H)\)?
We refer to the book [6] for notation and terminology not defined here. Information on the Ramsey numbers of well-known classes of graphs including paths, cycles, stars, and matchings can be found in [3, 4, 11, 10, 12, 13, 17].
For a positive integer \(m\), let \(K_{1, m}\) denote the star of size \(m\) and \(mK_2\) the matching of size \(m\). If \(s = (G_1, G_2, \ldots, G_m)\) is a Ramsey chain where either \(G_m= K_{1, m}\) or \(G_m = mK_2\), then \(G_i= K_{1, i}\) in the first case and \(G_i = iK_2\) in the second case for \(1 \le i \le m\). Since \(TR(K_{1, m}) = R(K_{1, m})\) for all \(m \ge 2\), we have the following result on stars.
Theorem 1.4. If \(s\) is a Ramsey chain with target link \(K_{1, m}\) for a positive integer \(m\), then \[TR(s) = R(K_{1, m}).\]
Since \(TR(mK_2) = R(mK_2)\) for \(2 \le m \le 5\), we have the following result for matchings of these sizes.
Theorem 1.5. If \(s\) is a Ramsey chain with target link \(mK_2\) where \(2 \le m \le 5\), then \[TR(s)= R(mK_2).\]
We will show that many other graphs \(H\) have the property that \(TR(s)=R(H)\) for every Ramsey chain \(s\) with target link \(H\) including all graphs of size 3 or \(4\).
In this section, we show that for every Ramsey chain \(s=(G_1, G_2, G_3)\) with target link of size \(3\), it follows that \(TR(s)=R(G_3)\). If \(G_3\) is a graph of size \(3\) without isolated vertices, then \[G_3\in \{P_4, K_3, P_3+K_2, K_{1, 3}, 3K_2\}.\]
By Theorems 1.4 and 1.5, if \(G_3= K_{1, 3}\) or \(G_3= 3K_2\), then \(TR(s)=R(G_3)\). Hence, it remains to consider \(G_3\in \{P_4, K_3, P_3+K_2\}\). For these graphs, Ramsey numbers are \(R(P_4) = 5\) and \(R(K_3) = R(P_3+K_2) = 6\) (see [4, 15, 17]). First, we present a known lemma (see [6]). The matching (edge-independence) number \(\alpha'(G)\) of a graph \(G\) is the maximum number of independent edges in \(G\).
Lemma 2.1. If \(G\) is a graph of size \(m\) with maximum degree \(\Delta\), then \(\displaystyle{\alpha'(G) \ge \left\lceil{\frac{m}{\Delta}}\right\rceil}\).
Theorem 2.2. If \(s\) is a Ramsey chain with target link \(G_3\) of size \(3\), then \(TR(s)=R(G_3)\).
Proof. Let \(s=(G_1, G_2, G_3)\) be a Ramsey chain where \(G_3\in \{ P_4, K_3, P_3+K_2 \}\). By Observation 1.3, it suffices to show that \(TS(s)\le R(G_3)\). We consider two cases, according to whether \(R(G_3) = 5\) or \(R(G_3) = 6\).
Case \(1\). \(R(G_3) = 5\). Then \(G_3=P_4\) and \(G_2\in \{P_3, 2K_2\}\). Let there be given a red-blue coloring of \(G=K_{5}\) with \(V(G)=\{v_1, v_2, \ldots, v_{5}\}\). Then there is a monochromatic subgraph \(G_3=P_4\) of \(G\), say \(G_3=(v_1, v_2, v_3, v_4)\). The graph \(H = G – E(G_3)\) has order 5 and size 7. Since two of the four edges \(v_5v_i\) (\(1 \le i \le 4\)) have the same color, there is a monochromatic subgraph \(G_2=P_3\) in \(H\). Thus, we may assume that \(G_2= 2K_2\). Let \(H_r\) and \(H_b\) be the red and blue subgraphs of \(H\) with \(|E(H_r)|\ge |E(H_b)|\), say. Thus, \(H_r\) has order 5 and size at least 4. If \(H_r\) does not contain \(2K_2\), then \(H_r=K_{1, 4}\) with \(E(H_r)=\{v_5v_i : 1\le i \le 4\}\). If one of the two edges \(v_1v_3\) and \(v_2v_4\) of \(H\) is red, say \(v_1v_3\) is red, then there is a red \(G_2=2K_2\) with \(E(G_2)=\{v_1v_3, v_2v_5\}\). Thus, we may assume that \(v_1v_3\) and \(v_2v_4\) are blue, producing a blue \(G_2=2K_2\) in \(H\). Since the size of \(G\) is 10 and \(|E(G_3)\cup E(G_2)| = 5\), there is always there is an edge in \(E(G)- [E(G_3)\cup E(G_2)]\) that is available for \(G_1= K_2\). Hence, there is a Ramsey chain \(s\) in \(G\). Therefore, \(TR(s)\le 5\) and so \(TR(s)=5\).
Case \(2\). \(R(G_3) = 6\). Then \(G_3\in \{K_3, P_3+K_2 \}\). If \(G_3= K_3\), then \(G_2= P_3\); while if \(G_3= P_3+K_2\), then \(G_2 \in\{P_3, 2K_2\}\). Let there be given a red-blue coloring of \(G=K_{6}\) with \(V(G)=\{v_1, v_2, \ldots, v_{6}\}\). Since \(R(G_3) = 6\) where \(G_3\in \{K_3, P_3+K_2\}\), there is a monochromatic subgraph \(G_3\) of \(G\). Let \(H = G – E(G_3)\). We may assume that \(v_6 \notin V(G_3)\). Since at least two of the edges \(v_6v_i\) (\(1\le i \le 5\)) have the same color, there is a monochromatic subgraph \(G_2= P_3\) in \(H\). Thus, we may assume that \(G_2= 2K_2\). Let \(H_r\) and \(H_b\) be the red and blue subgraphs respectively of \(H\) where \(|E(H_r)|\ge |E(H_b)|\), say. Thus, \(H_r\) has order 6 and size at least \(6\). Since \(\Delta(H_r) \le 5\), it follows by Lemma 2.1 that \(\alpha'(H_r) \ge 2\) and so \(H_r\) contains the subgraph \(G_2= 2K_2\). Since the size of \(G\) is 15 and \(|E(G_3)\cup E(G_2)| = 5\), there is an edge in \(E(G)- [E(G_3)\cup E(G_2)]\) that is available for \(G_1= K_2\). Hence, there is a Ramsey chain \(s\) in \(G\). Therefore, \(TR(s)\le 6\) and so \(TR(s)=6\). \(\square\)
In this section, we establish the following result.
Theorem 3.1. If \(s\) is a Ramsey chain with target link \(G_4\) of size \(4\), then \(TR(s)=R(G_4)\).
If \(G_4\) is a graph of size \(4\) without isolated vertices, then \[G_4\in \{C_4, P_5, S_{3, 2}, K_{1, 3}+e, K_{1, 4}, K_3+K_2, K_{1, 3}+K_2, 2P_3, P_4+K_2, P_3+2K_2, 4K_2 \}.\]
By Theorems 1.4 and 1.5, if \(G_4 \in \{K_{1, 4}, 4K_2\}\), then \(TR(s)=R(G_4)\). Thus, we may assume that \(G_4\notin \{K_{1, 4}, 4K_2\}\). The Ramsey numbers of the other graphs of size 4 without isolated vertices are \(R(C_4)=R(P_5) = R(S_{2, 3})= 6\), \(R(K_{1, 3}+e) = R(K_3+K_2) =R(K_{1, 3}+K_2) = R(2P_3) = 7\), \(R(P_4+K_2)= 8\), and \(R(P_3+2K_2) = 9\) (see [4, 17]).
We now consider all Ramsey chains whose target link \(G_4\in\{C_4, P_5, S_{2, 3}\}\) has Ramsey number 6. First, the following lemma is presented.
Lemma 3.2. Every red-blue coloring of a graph of order \(6\) and size \(8\) results in a monochromatic \(P_3\).
Proof. Since every graph of order \(6\) and size \(8\) has a vertex \(v\) of degree 3 or more, every red-blue coloring of such a graph results in two edges of the same color incident with \(v\), producing a monochromatic \(P_3\). \(\square\)
Theorem 3.3. If \(s\) is a Ramsey chain with target link \(C_4\), then \(TR(s)=R(C_4)=6\).
Proof. By Observation 1.3, it suffices to show that \(TR(s)\le 6\). Let \(s= (G_1, G_2, G_3, G_4)\) be a Ramsey chain where \(G_4=C_4\). Then \(G_3=P_4\) and \(G_2 \in \{P_3, 2K_2\}\). Let there be given a red-blue coloring of \(G=K_6\) with \(V(G)=\{v_1, v_2, \ldots, v_6\}\). Since \(R(C_4)=6\), there is a monochromatic subgraph \(G_4=C_4\) in \(G\), say \(C_4=(v_1, v_2, v_3, v_4, v_1)\). We show that \(F=K_6-E(G_4)\) contains a monochromatic \(P_4\). Since at least two of the four edges \(v_5v_i\) (\(i = 1, 2, 3, 4\)) have the same color, we may assume that \(v_5v_a\) and \(v_5v_b\) are red where \(\{a, b\}= \{1, 2\}\) or \(\{a, b\} = \{1, 3\}\). We consider these two cases.
Case \(1\). The edges \(v_1v_5\) and \(v_2v_5\) are red. If one of \(v_1v_6\) and \(v_2v_6\) is red, there is a red \(P_4\) in \(F\). Thus, we may assume that \(v_1v_6\) and \(v_2v_6\) are blue. If \(v_1v_3\) is red, then \((v_3, v_1, v_5, v_2)\) is a red \(G_3=P_4\) in \(F\). If \(v_1v_3\) is blue, then \((v_3, v_1, v_6, v_2)\) is a blue \(G_3=P_4\) in \(F\).
Case \(2\). The edges \(v_1v_5\) and \(v_3v_5\) are red. By Case 1, we may assume that \(v_2v_5\) and \(v_4v_5\) are blue. By the argument in Case 1, we may further assume that \(v_1v_6\) and \(v_3v_6\) are blue and \(v_2v_6\) and \(v_4v_6\) are red; for otherwise, there is a monochromatic \(P_4\). Then regardless of the color of \(v_5v_6\), there is a monochromatic subgraph \(G_3=P_4\).
Next, let \(H=G-[E(C_4)\cup E(P_4)]\). Since \(H\) has order 6 and size 8, it follows by Lemma 3.2 that \(H\) contains a monochromatic subgraph \(G_2= P_3\). Thus, it remains to show that \(H\) contains a monochromatic \(G_2= 2K_2\). Assume, to the contrary, that \(H\) contains no monochromatic \(2K_2\). We verify the following claim.
Claim: If \(H\) contains no monochromatic \(2K_2\), then the red subgraph \(H_r\) of \(H\) and the blue subgraph \(H_b\) of \(H\) are both stars.
Suppose that the claim is false. The only graphs (without isolated vertices) that contain no \(2K_2\) are stars and the triangle \(K_3\). Because the size of \(H\) is 8, one of \(H_r\) and \(H_b\) is a star and the other is \(K_3\), say \(H_r=K_{1, 5}\) centered at a vertex \(v_p\) and \(H_b = K_3\). Since \(\deg_H v_i \le 3\) for \(1 \le i \le 4\), it follows that \(v_p \in \{v_5, v_6\}\), say \(v_p = v_6\). Then \(E(H_r)=\{v_6v_i: 1 \le i \le 5\}\). Since \(E(C_4) \cap E(P_4) = \emptyset\) and \(C_4=(v_1, v_2, v_3, v_4, v_1)\), it follows that either \(v_1v_3 \notin E(P_4)\) or \(v_2v_4\notin E(P_4)\), say the former. Thus, \(v_1v_3 \in E(H_b)\) and so \(H_b=(v_1, v_3, v_5, v_1)\). Then \(E(G) – [E(C_4)\cup E(H)]=\{v_2v_4, v_4v_5, v_5v_2\}\), which forms the triangle \((v_2, v_4, v_5, v_2)\). On the other hand, \(E(P_4)= E(G) – [E(C_4)\cup E(H)]\), which is impossible. This verifies the claim.
Next, suppose that \(H_r = K_{1, s}\) is centered at a vertex \(v_p\) and \(H_b = K_{1, t}\) is centered at a vertex \(v_q\) where \(s+t = 8\). We may assume that \(s \ge t\) and so \(s \in \{4, 5\}\) and \(t \ge 3\). By the argument used in verifying the claim, we may assume that (1) \(v_p \in \{v_5, v_6\}\), say \(v_p = v_6\), and (2) \(v_1v_3 \in E(H)\) and so \(v_q \in \{v_1, v_3\}\), say \(v_q = v_3\). Since \(3 \le t =\deg_{H_b} v_3 \le \deg_{H} v_3 = 3\), it follows that \(t = 3\) and \(s = 5\). Then \(v_6v_i\in E(H_r)\) for \(1 \le i \le 5\). However then, \(v_3\) is adjacent only to \(v_1\) and \(v_5\) in \(H_b\) and so \(\deg_{H_b} v_3 = 2\), which is a contradiction. Thus, \(H\) contains a monochromatic \(2K_2\). Since \(E(G)-[E(G_4)\cup E(G_3)\cup E(G_2)] \ne \emptyset\), there is a monochromatic subgraph \(G_1=K_2\) that is edge-disjoint from \(G_i\) for \(i = 2, 3, 4\). Therefore, \(s\) is a Ramsey chain in \(G\) and so \(TR(s)\le 6\). Therefore, \(TR(s)=R(C_4)=6\). \(\square\)
To show that \(TR(s)=R(P_5)\) for every Ramsey chain \(s\) with target link \(P_5\), we first present some preliminary results.
Lemma 3.4. If \(A\) and \(B\) are two edge-disjoint monochromatic subgraphs of a red-blue coloring of \(G=K_6\) where \(A= P_5\) and \(B\) has size \(3\) without isolated vertices such that \(G – [E(A) \cup E(B)]\) has no monochromatic \(2K_2\), then \(B = P_4\).
Proof. Let \(G = K_6\) with \(V(G) = \{v_1, v_2, \ldots, v_6\}\) such that \(H= G – [E(A) \cup E(B)]\) has no monochromatic \(2K_2\). We may assume that \(A = P_5=(v_1, v_2, \ldots, v_5)\). Let \(H_r\) and \(H_b\) be the red and blue subgraphs of \(H\) where \(|E(H_r)| \ge |E(H_b)|\), say. Since the size of \(H\) is \({6 \choose 2} – 7= 8\) and \(H\) has no monochromatic \(2K_2\), it follows that either (1) \(H_r= K_{1, 5}\) and \(H_b= K_3\) or (2) \(H_r\) and \(H_b\) are stars. We consider these two cases.
Case \(1\). \(H_r= K_{1, 5}\) and \(H_b= K_3\). Then \(H_r\) is centered at \(v_6\) and \(E(H_r)=\{v_6v_i: 1 \le i \le 5\}\). Thus, \(H_b =K_3= (v_1, v_3, v_5, v_1)\). Hence, \(E(B)=\{v_1v_4, v_4v_2, v_2v_5\}\) and so \(B = (v_1, v_4, v_2, v_5) =P_4\). The subgraph induced by \(E(A)\cup E(H)\) is illustrated in Figure 1, where an edge in \(A\) is indicated by a dotted line, a red edge in \(H_r\) is indicated by a bold line, and a blue edge in \(H_b\) is indicated by a thin line, and \(E(B) = E(G) -[E(A)\cup E(H)]\).
Case \(2\). \(H_r\) and \(H_b\) are stars. Let \(H_r = K_{1, s}\) centered at a vertex \(v_p\) and \(H_b = K_{1, t}\) centered at a vertex \(v_q\) where \(s \ge t\) and \(s+t = 8\). Thus, \(s \in \{4, 5\}\) and \(t \ge 3\).
\(\star\) If \(s > t\), then \(s = 5\) and \(t = 3\). Then \(v_p = v_6\) and \(E(H_r)=\{v_6v_i: 1 \le i \le 5\}\). This implies that \(v_q \in \{v_1, v_5\}\), say \(v_q = v_1\). Then \(E(H_b)=\{v_1v_i: \ i =3, 4, 5\}\). Hence, \(E(B)=\{v_4v_2, v_2v_5, v_5v_3\}\) and so \(B = (v_4, v_2, v_5, v_3) =P_4\). The subgraph induced by \(E(A)\cup E(H)\) is illustrated in Figure 1 when \(v_q = v_1\) and \(E(B) = E(G) -[E(A)\cup E(H)]\).
\(\star\) If \(s = t\), then \(s = t = 4\). Since \(\deg_H v_i \le 3\) for \(i =2, 3, 4\), it follows that \(v_p, v_q \in \{v_1, v_5, v_6\}\). If \(\{v_p, v_q\}\subseteq\{v_1, v_5\}\), then \(v_pv_q \in E(H_r)\cap E(H_b)\), which is a contradiction. Thus, we may assume that \(v_p = v_6\) and \(v_q= v_1\). Then \(E(H_b)=\{v_1v_i: \ i =3, 4, 5, 6\}\) and \(E(H_r)=\{v_6v_i: 2 \le i \le 5\}\). Hence, \(E(B)=\{v_4v_2, v_2v_5, v_5v_3\}\) and so \(B = (v_4, v_2, v_5, v_3) =P_4\). The subgraph induced by \(E(A)\cup E(H)\) is illustrated in Figure 1 when \(v_q = v_1\) and \(E(B) = E(G) -[E(A)\cup E(H)]\). \(\square\)
The following is a consequence of the proof of Lemma 3.4.
Corollary 3.5. For the graph \(G= K_6\) with a red-blue coloring where \(V(G)=\{v_1, v_2, \ldots, v_6\}\), let \(A= P_5= (v_1, v_2, \ldots, v_5)\) and \(B\) be two edge-disjoint monochromatic subgraphs of \(G\) where \(B\) has size \(3\) without isolated vertices. Furthermore, let \(H=G – [E(A) \cup E(B)]\) with red subgraph \(H_r\) and blue subgraph \(H_b\) where \(|E(H_r)| \ge |E(H_b)|\). If \(H\) has no monochromatic \(2K_2\), then \(B = P_4\) and one of the following occurs:
\((1)\) \(H_r = K_{1, 5}\) is centered at \(v_6\) and \(H_b = K_3\),
\((2)\) \(H_r = K_{1, 5}\) is centered at \(v_6\) and \(H_b = K_{1, 3}\) is centered at \(v_q \in \{v_1, v_5\}\), and
\((3)\) \(H_r = H_b= K_{1, 4}\) where \(H_r\) is centered at \(v_6\) and \(H_b\) is centered at \(v_q \in \{v_1, v_5\}\).
If \((1)\) occurs, then \(B = (v_1, v_4, v_2, v_5)\); while if \((2)\) or \((3)\) occurs, then \(B=(v_4, v_2, v_5, v_3)\) if \(v_q = v_1\) or \(B=(v_3, v_1, v_4, v_2)\) if \(v_q = v_5\).
A graph \(G\) is \(F\)-free for some graph \(F\) if \(G\) contains no subgraph isomorphic to \(F\).
Lemma 3.6. If \(G\) is a graph of order \(6\) and size at least \(6\) that is \((P_3 + K_2)\)-free, then \(G = K_4+ 2K_1\).
Proof. Let \(G\) be a graph of order \(6\) and size \(m \ge 6\) that is \((P_3 + K_2)\)-free. Since the order of \(G\) is 6 and \(m \ge 6\), it follows that \(2 \le \Delta(G) \le 5\).
\(\star\) If \(\Delta(G) = 2\), then \(G = 2K_3\) or \(G = C_6\). Since \(P_3 + K_2\subseteq 2K_3\) and \(P_3 + K_2\subseteq C_4\), it follows that \(P_3 + K_2\subseteq G\).
\(\star\) If \(\Delta(G) = 3\), let \(v\) be a vertex of degree 3 and \(N(v)=\{v_1, v_2, v_3\}\). If there is an edge \(e \in E(G)- \{vv_i: i = 1, 2, 3\}\) that is not incident with two vertices in \(\{v_1, v_2, v_3\}\), say \(e\) is not incident with \(v_1\) and \(v_2\), then \(P_3 + K_2\subseteq G\), where \(P_3=(v_1, v, v_2)\) and \(E(K_2) =\{e\}\). If every edge in \(E(G)- \{vv_i: i = 1, 2, 3\}\) joins two vertices in \(\{v_1, v_2, v_3\}\), then \(m = 6\) and \(G = K_4+ 2K_1\) where \(V(K_4)=\{v, v_1, v_2, v_3\}\).
\(\star\) If \(\Delta(G) \in \{4, 5\}\), let \(v\) be a vertex of degree \(\Delta(G)\). For \(\Delta(G) = 4\), let \(N(v)=\{v_1, v_2, v_3, v_4\}\); while for \(\Delta(G) = 5\), let \(N(v)=\{v_1, v_2, v_3, v_4, v_5\}\). If there is an edge joining two vertices in \(N(v)\), then \(G\) contains \(K_{1, 4}+e\) as a subgraph. If \(N(v)\) is an independent set of vertices of \(G\), then \(\Delta(G)= 4\) and some vertex in \(N(v)\) is adjacent to \(v_5\). Thus, \(G\) contains the double star \(S_{2, 4}\) as a subgraph. Since \(P_3 + K_2\subseteq K_{1, 4}+e\) and \(P_3 + K_2\subseteq S_{2, 4}\), it follows that \(P_3 + K_2\subseteq G\). \(\square\)
Theorem 3.7. If \(s\) is a Ramsey chain with target link \(P_5\), then \(TR(s)=R(P_5)=6\).
Proof. By Observation 1.3, it suffices to show that \(TR(s)\le 6\). Let \(s= (G_1, G_2, G_3, G_4)\) be a Ramsey chain where \(G_4=P_5\) and \(G_3\in \{ P_4, P_3+K_2\}\). Then \(G_2 \in \{P_3, 2K_2\}\). Let there be given a red-blue coloring of \(G=K_6\) with \(V(G)=\{v_1, v_2, \ldots, v_6\}\). Since \(R(P_5)=6\), there is a monochromatic subgraph \(G_4=P_5\) of \(G\) where \(P_5=(v_1, v_2, v_3, v_4, v_5)\) say, and let \(F=K_6-E(G_4)\) with red subgraph \(F_r\) and blue subgraph \(F_b\). We may assume that \(|E(F_r)| \ge |E(F_b)|\). We show that \(F\) contains a monochromatic subgraph \(G_3 \in \{P_4, P_3+K_2\}\). There are two possibilities.
Case \(1\). \(G_3 = P_4\). Since at least two of the three edges \(v_6v_1, v_6v_2, v_6v_3\) have the same color, we may assume that \(v_iv_6\) and \(v_jv_6\) are red where \(1 \le i < j \le 3\). If one of \(v_iv_5\) and \(v_jv_5\) is red, then there is a red \(P_4\) in \(F\). Thus, we may assume that \(v_iv_5\) and \(v_jv_5\) are blue. Then regardless of the color of \(v_iv_4\), there is a monochromatic subgraph \(G_3=P_4\) in \(F\).
Case \(2\). \(G_3 = P_3+K_2\). Since \(|E(F_r)| \ge |E(F_b)|\) and \(|E(F)|= 11\), it follows that \(F_r\) is a graph of order 6 and size at least 6. If \(P_3 + K_2 \subseteq F_r\), then there is a red \(G_3= P_3+K_2\). If \(F_r\) does not contain \(P_3+K_2\), then \(F_r = K_4+2K_1\) by Lemma 3.6. This implies that \(V(K_4)= \{v_1, v_3, v_5, v_6\}\). Thus, \(F_b\) contains \(G_3= P_3+K_2\) where \(P_3=(v_1, v_4, v_6)\) and \(K_2=(v_2, v_5)\).
Next, let \(H= G- [E(G_4)\cup E(G_3)]\). It then follows by Lemma 3.2 that \(H\) contains a monochromatic \(P_3\). Thus, if \(G_2= P_3\), then \(s\) is a Ramsey chain in \(G\). Hence, we may assume that \(G_2= 2K_2\). By Lemma 3.4, if \(G_3 = P_3+K_2\), then \(H\) contains a monochromatic subgraph \(G_2= 2K_2\) and so \(s\) is a Ramsey chain in \(G\). Hence, we may assume that \(G_3= P_4\). By Corollary 3.5, there are three possibilities:
\((1)\) \(H_r = K_{1, 5}\) is centered at \(v_6\) and \(H_b = K_3\).
\((2)\) \(H_r = K_{1, 5}\) is centered at \(v_6\) and \(H_b = K_{1, 3}\) is centered at \(v_q \in \{v_1, v_5\}\).
\((3)\) \(H_r = H_b= K_{1, 4}\) where \(H_r\) is centered at \(v_6\) and \(H_b\) is centered at \(v_q \in \{v_1, v_5\}\).
Furthermore, if \((1)\) occurs, then \(G_3= P_4=(v_1, v_4, v_2, v_5)\) is monochromatic; while if \((2)\) or \((3)\) occurs, then we may assume that \(v_q = v_1\) and so \(G_3 =P_4= (v_4, v_2, v_5, v_3)\) is monochromatic. Depending on whether \(G_4= P_5\) is red or blue, we construct a new Ramsey chain \(A_1= K_2, A_2 = 2K_2, A_3 = P_4, A_4= P_5\) as follows.
\(\star\) If \((1)\) occurs, then \(G_3 =P_4= (v_1, v_4, v_2, v_5)\) is monochromatic. If \(P_5= (v_1, v_2, v_3, v_4, v_5)\) is red, let \(A_4=(v_1, v_2, v_6, v_4, v_5)\) be a red \(P_5\) and \(A_3=(v_2, v_3, v_6, v_5)\) a red \(P_4\). If \(P_5=(v_1, v_2, v_3, v_4, v_5)\) is blue, let \(A_4= (v_1, v_2, v_3, v_5, v_4)\) be a blue \(P_5\) and \(A_3=(v_4, v_3, v_1, v_5)\) a blue \(G_3=P_4\). This is illustrated in Figure 3 where an edge in \(A_i\) is labeled \(i\) for \(i \in \{3, 4\}\). Thus, \(A_4\) and \(A_3\) are edge-disjoint.
\(\star\) If (2) or (3) occurs, then \(G_3 =P_4= (v_4, v_2, v_5, v_3)\) is monochromatic. First, suppose that (2) occurs. If \(P_5= (v_1, v_2, v_3, v_4, v_5)\) is red, let \(A_4=(v_1, v_2, v_6, v_4, v_5)\) be a red \(P_5\) and \(A_3=(v_2, v_3, v_6, v_5)\) a red \(P_4\). If \(P_5=(v_1, v_2, v_3, v_4, v_5)\) is blue, let \(A_4= (v_2, v_1, v_5, v_4, v_3)\) be a blue \(P_5\) and \(A_3=(v_2, v_3, v_1, v_4)\) a blue \(G_3=P_4\). This is illustrated in Figure 4 and so \(A_4\) and \(A_3\) are edge-disjoint.
Next, suppose that (3) occurs. If \(P_5= (v_1, v_2, v_3, v_4, v_5)\) is red, let \(A_4=(v_1, v_2, v_6, v_4, v_5)\) be a red \(P_5\) and \(A_3=(v_2, v_3, v_6, v_5)\) a red \(P_4\). If \(P_5= (v_1, v_2, v_3, v_4, v_5)\) is blue, let \(A_4=(v_6, v_1, v_5, v_4, v_3)\) be a blue \(P_5\) and \(A_3=(v_3, v_2, v_1, v_4)\) a blue \(G_3=P_4\). This is illustrated in Figure 5 and so \(A_4\) and \(A_3\) are edge-disjoint.
In either situation, the monochromatic subgraph \(G_3 =P_4= (v_4, v_2, v_5, v_3)\) is edge-disjoint from \(A_4\) and \(A_3\) and can be decomposed into \(A_2=2K_2\) and \(A_1= K_2\). Therefore, \(A_1, A_2, A_3, A_4\) are pairwise edge-disjoint. Thus, \(s\) is a Ramsey chain in \(G\). \(\square\)
Next, we show that \(TR(s) = R(S_{2, 3})\) for every Ramsey chain \(s\) with target link \(S_{2, 3}\). First, we present a lemma.
Lemma 3.8. If \(A= S_{2, 3}\) and \(B\) are two edge-disjoint monochromatic subgraphs of the graph \(G = K_6\) with a red-blue coloring where \(B\) has size \(3\) without isolated vertices such that \(G – [E(A) \cup E(B)]\) has no monochromatic \(2K_2\), then \(B \in \{P_3+K_2, K_3, P_4\}\).
Proof. Let \(G = K_6\) with \(V(G)=\{v_1, v_2, \ldots, v_6\}\). Since \(R(S_{2, 3})=6\), there is a monochromatic subgraph \(A=S_{2, 3}\). We may assume that \(A\) is obtained from the 4-path \((v_2, v_3, v_4, v_5)\) by adding the edge \(v_1v_3\). Suppose that \(H= G- [E(A)\cup E(B)]\) does not contain monochromatic \(2K_2\). Let \(H_r\) and \(H_b\) be the red and blue subgraphs of \(H\) where \(|E(H_r)| \ge |E(H_b)|\), say. Since the size of \(H\) is \({6 \choose 2} – 7= 8\) and \(H\) has no monochromatic \(2K_2\), it follows that either (1) \(H_r= K_{1, 5}\) and \(H_b= K_3\) or (2) \(H_r\) and \(H_b\) are stars. We consider these two cases.
Case \(1\). \(H_r= K_{1, 5}\) and \(H_b= K_3\). Then \(H_r\) is centered at \(v_6\) and \(E(H_r)=\{v_6v_i: 1 \le i \le 5\}\). Thus, \(H_b =K_3= (v_1, v_2, v_5, v_1)\). Hence, \(E(B)=\{v_1v_4, v_4v_2, v_3v_5\}\) and so \(B = P_3+K_2\).
Case \(2\). \(H_r\) and \(H_b\) are stars. Suppose that \(H_r = K_{1, s}\) is centered at a vertex \(v_p\) and \(H_b = K_{1, t}\) is centered at a vertex \(v_q\) where \(s+t = 8\), \(s \ge t\), \(s \in \{4, 5\}\), and \(t \ge 3\).
\(\star\) If \(s > t\), then \(s = 5\) and \(t = 3\). Then \(v_p = v_6\) and \(E(H_r)=\{v_6v_i: 1 \le i \le 5\}\). This implies that \(v_q \in \{v_1, v_2, v_5\}\). Thus, \(v_q = v_1\) or \(v_q = v_5\). If \(v_q = v_1\), then \(E(H_b)=\{v_1v_i: \ i =2, 4, 5\}\). Hence, \(E(B)=\{v_4v_2, v_2v_5, v_5v_3\}\) and so \(B = (v_4, v_2, v_5, v_3) = P_4\). If \(v_q =v_5\), then \(E(H_b)=\{v_5v_i: \ i = 1, 2, 3\}\). Hence, \(E(B)=\{v_1v_2, v_2v_4, v_4v_1\}\) and so \(B = (v_1, v_2, v_4, v_1) =K_3\).
\(\star\) If \(s = t\), then \(s = t = 4\). Since \(\deg_H v_i \le 3\) for \(i =3, 4\), it follows that \(v_p, v_q \in \{v_1, v_2, v_5, v_6\}\). If \(\{v_p, v_q\}\subseteq\{v_1, v_2, v_5\}\), then \(v_pv_q \in E(H_r)\cap E(H_b)\), which is a contradiction. Thus, we may assume that \(v_p = v_6\) and \(v_q \in \{v_1, v_5\}\). If \(v_q = v_1\), then \(E(H_b)=\{v_1v_i: \ i =2, 4, 5, 6\}\) and \(E(H_r)=\{v_6v_i: 2 \le i \le 5\}\). Hence, \(E(B)=\{v_4v_2, v_2v_5, v_5v_3\}\) and so \(B = (v_4, v_2, v_5, v_3) = P_4\). If \(v_q =v_5\), then \(E(H_b)=\{v_5v_i: \ i = 1, 2, 3, 6\}\) and \(E(H_r)=\{v_6v_i: 1 \le i \le 4\}\). Hence, \(E(B)=\{v_1v_2, v_2v_4, v_4v_1\}\) and so \(B = (v_1, v_2, v_4, v_1) =K_3\). \(\square\)
The following is a consequence of Lemma 3.8.
Corollary 3.9. Let \(G= K_6\) with a red-blue coloring where \(V(G)=\{v_1, v_2, \ldots, v_6\}\), let \(A= S_{2, 3}\) and \(B\) be two edge-disjoint monochromatic subgraphs of \(G\) where \(E(A)=\{v_1v_3, v_2v_3, v_3v_4, v_4v_5\}\) and \(B\) has size \(3\) without isolated vertices, and let \(H=G – [E(A) \cup E(B)]\) with red subgraph \(H_r\) and blue subgraph \(H_b\) where \(|E(H_r)| \ge |E(H_b)|\). If \(H\) has no monochromatic \(2K_2\), then \(B \in \{P_3+K_2, K_3, P_4\}\). Furthermore
\((a)\) \(B = P_3+K_2\) only when \(H_r = K_{1, 5}\) is centered at \(v_6\), \(H_b = K_3=(v_1, v_2, v_5, v_1)\), and \(E(B)=\{v_1v_4, v_4v_2, v_3v_5\}\) and
\((b)\) \(B = P_4\) only when one of the following occurs
\((1)\) \(H_r = K_{1, 5}\) is centered at \(v_6\) and \(H_b = K_{1, 3}\) is centered at \(v_q\in \{v_1, v_2\}\).
\((2)\) \(H_r = H_b = K_{1, 4}\) where \(H_r\) is centered at \(v_6\) and \(H_b\) is centered at \(v_q\in \{v_1, v_2\}\).
Theorem 3.10. If \(s\) is a Ramsey chain with target link \(S_{2, 3}\), then \(TR(s)=R(S_{2, 3})=6\).
Proof. By Observation 1.3, it suffices to show that \(TS(s)\le 6\). Let \(s= (G_1, G_2, G_3, G_4)\) be a Ramsey chain where \(G_4=S_{2, 3}\). Then \(G_3 \in \{P_4, K_{1, 3}, P_3+K_2\}\) and \(G_2 \in \{P_3, 2K_2\}\). Let there be given a red-blue coloring of \(G=K_6\) with \(V(G)=\{v_1, v_2, \ldots, v_6\}\). Since \(R(S_{2, 3})=6\), in the red-blue coloring of \(G\), there is a monochromatic subgraph \(G_4=S_{2, 3}\) obtained, say, from the 4-path \((v_2, v_3, v_4, v_5)\) by adding the edge \(v_1v_3\). We show that \(F=K_6-E(G_4)\) contains a monochromatic subgraph \(G_3 \in \{K_{1, 3}, P_4, P_3+K_2\}\). There are three possibilities.
Case \(1\). \(G_3= K_{1, 3}\). Since at least three of the five edges \(v_6v_i\) (\(1 \le i \le 5\)) have the same color, there is a monochromatic subgraph \(G_3= K_{1, 3}\) in \(F\).
Case \(2\). \(G_3= P_4\). Since at least two of the three edges \(v_6v_1, v_6v_2, v_6v_3\) have the same color, we may assume that \(v_6v_i\) and \(v_6v_j\) are red where \(1 \le i < j \le 3\), where either \(\{i, j\} = \{1, 2\}\) or \(\{i, j\} = \{1, 3\}\). If one of \(v_5v_i\) and \(v_5v_j\) is red, then there is a red \(P_4\) in \(F\). Thus, we may assume that \(v_5v_i\) and \(v_5v_j\) are blue. Regardless of the color of \(v_1v_4\), there is a monochromatic subgraph \(G_3=P_4\) in \(F\).
Case \(3\). \(G_3= P_3+ K_2\). Since at least two of the three edges \(v_6v_1, v_6v_2, v_6v_3\) have the same color, we may assume that \(v_iv_6\) and \(v_jv_6\) are red where \(1 \le i < j \le 3\) and either \(\{i, j\}= \{1, 2\}\) or \(\{i, j\} = \{1, 3\}\).
Subcase \(3.1\). \(v_6v_1\) and \(v_6v_2\) are red. Then \(v_3v_5\) is blue, for otherwise, \((v_1, v_6, v_2) + (v_3, v_5)\) is a red \(P_3+K_2\). The edge \(v_2v_4\) is either red or blue.
\(\star\) If \(v_2v_4\) is red, then \(v_1v_5\) is blue, for otherwise \((v_6, v_2, v_4) + (v_1, v_5)\) is a red \(P_3+K_2\). Then \(v_6v_4\) is red, for otherwise \((v_1, v_5, v_3) + (v_6, v_4)\) is a blue \(P_3+K_2\).
\(\circ\) If \(v_6v_3\) is red, then \((v_1, v_6, v_3) + (v_2, v_4)\) is a red \(P_3+K_2\).
\(\circ\) If \(v_6v_3\) is blue, then \(v_1v_2\) is red, for otherwise \((v_6, v_3, v_5)+(v_1, v_2)\) is a blue \(P_3+K_2\). This implies that \(v_6v_5\) is blue, for otherwise, \((v_1, v_2, v_4)+(v_6, v_5)\) is a red \(P_3+K_2\). Regardless of the color of \(v_1v_4\), there is a monochromatic \(P_3+K_2\).
\(\star\) If \(v_2v_4\) is blue, then \(v_6v_3, v_6v_4, v_6v_5\) are red, for otherwise there is a blue \(P_3+K_2\). Regardless of the color of \(v_1v_2\), there is a monochromatic \(P_3+K_2\).
Subcase \(3.2\). \(v_6v_1\) and \(v_6v_3\) are red. Then \(v_2v_4\) and \(v_2v_5\) are blue, for otherwise there is a red \(P_3+K_2\). Consider the color of the edge \(v_1v_2\).
\(\star\) If \(v_1v_2\) is red, then \(v_3v_5\) is blue, for otherwise \((v_6, v_1, v_2) + (v_3, v_5)\) is a red \(P_3+K_2\). Then \(v_6v_4\) is red, for otherwise \((v_3, v_5, v_2) + (v_6, v_4)\) is a blue \(P_3+K_2\). Then \((v_3, v_6, v_4)+(v_1, v_2)\) is a red \(P_3+K_2\).
\(\star\) If \(v_1v_2\) is blue, then \(v_6v_4\) is red, for otherwise \((v_1, v_2, v_5) + (v_6, v_4)\) is a blue \(P_3+K_2\). Then \(v_1v_5\) is blue, for otherwise \((v_3, v_6, v_4) + (v_1, v_5)\) is a red \(P_3+K_2\). Then \(v_3v_5\) is red, for otherwise \((v_4, v_2, v_1) + (v_3, v_5)\) is a blue \(P_3+K_2\). There is a red \(P_3+K_2 = (v_1, v_6, v_4) + (v_3, v_5)\).
Next, let \(H= G- [E(G_4)\cup E(G_3)]\). It then follows by Lemma 3.2 that \(H\) contains a monochromatic \(P_3\). Thus, if \(G_2= P_3\), then \(s\) is a Ramsey chain in \(G\). Hence, we may assume that \(G_2= 2K_2\). Then \(G_3\in \{P_3+K_2, P_4\}\).
\(\bullet\) If \(G_3= P_3+K_2\), then it follows by Corollary 3.9 that \(H_r = K_{1, 5}\) is centered at \(v_6\), \(H_b = K_3=(v_1, v_2, v_5, v_1)\), and \(G_3=P_3+K_2= (v_1, v_4, v_2) + (v_3, v_5)\). Depending on whether \(G_4= S_{2, 3}\) is red or blue, we construct a new Ramsey chain \[A_1= K_2, A_2= 2K_2, A_3 = P_3+K_2, A_4= S_{2, 3},\] as follows.
\(\star\) First, suppose that \(G_4= S_{2, 3}\) is red. Then \(A_4= S_{2, 3}\) is red obtained from \(P_4=(v_2, v_3, v_6, v_4)\) by adding the edge \(v_6v_5\) and \(A_3=P_3+K_2=(v_3, v_4, v_5)+ (v_1, v_6)\) is red. The monochromatic subgraph \(G_3 =P_3+ K_2\) is edge-disjoint from \(A_4\) and \(A_3\) and can be decomposed into \(A_2=2K_2\) and \(A_1= K_2\).
\(\star\) Next, suppose that \(G_4= S_{2, 3}\) is blue.
\(\circ\) If \(G_3=P_3+K_2= (v_1, v_4, v_2) + (v_3, v_5)\) is red, then \(A_4= S_{2, 3}\) is red obtained from \(P_4=(v_2, v_4, v_6, v_3)\) by adding the edge \(v_6v_5\), \(A_3=P_3+K_2=(v_6, v_1, v_4)+ (v_2, v_5)\) is red, \(A_2= 2K_2\) is blue with \(E(A_2) = \{v_1v_2, v_3v_4\}\), and \(A_1= K_2\).
\(\circ\) If \(G_3=P_3+K_2= (v_1, v_4, v_2) + (v_3, v_5)\) is blue, then \(A_4= S_{2, 3}\) is blue obtained from \(P_4=(v_5, v_2, v_1, v_3)\) by adding the edge \(v_1v_4\), \(A_3=P_3+K_2=(v_2, v_4, v_3)+ (v_1, v_5)\) is blue, \(A_2= 2K_2\) is blue with \(E(A_2) = \{v_2v_3, v_4v_5\}\), and \(A_1= K_2\).
\(\bullet\) If \(G_3= P_4\), then there are two possibilities by Corollary 3.9, namely,
(1) \(H_r = K_{1, 5}\) centered at \(v_p= v_6\) and \(H_b = K_{1, 3}\) centered at \(v_q\in \{v_1, v_2\}\), or
(2) \(H_r = K_{1, 4}\) centered at \(v_p= v_6\) and \(H_b = K_{1, 4}\) centered at \(v_q\in \{v_1, v_2\}\).
In either (1) or (2) occurs, we may assume that \(v_q = v_1\). Depending on whether \(G_4= S_{2, 3}\) is red or blue, we construct a new Ramsey chain \[A_1= K_2, A_2 = 2K_2, A_3 = P_4, A_4= S_{2, 3},\] as follows.
\(\star\) First, suppose that (1) occurs. Then \(E(H_r)=\{v_6v_i: 1 \le i \le 5\}\) and \(E(H_b)=\{v_1v_i: \ i =2, 4, 5\}\).
\(\circ\) If \(G_4\) is red, then \(A_4= S_{2, 3}\) is red obtained from \(P_4=(v_1, v_3, v_4, v_5)\) by adding the edge \(v_4v_6\) and \(A_3=P_4=(v_3, v_2, v_6, v_5)\) is red.
\(\circ\) If \(G_4\) is blue, then then \(A_4= S_{2, 3}\) is blue obtained from \(P_4=(v_3, v_2, v_1, v_4)\) by adding the edge \(v_1v_5\) and \(A_3=P_4=(v_1, v_3, v_4, v_5)\) is blue.
\(\star\) Next, suppose that (2) occurs. Then \(E(H_r)=\{v_6v_i: 2 \le i \le 5\}\) and \(E(H_b)=\{v_1v_i: \ i =2, 4, 5, 6\}\). For \(A_4\) and \(A_3\) in situation (1), the edge \(v_1v_6\) is not used. Thus, regardless of the color of \(G_4\), there are edge-disjoint monochromatic subgraphs \(A_4=S_{2, 3}\) and \(A_3= P_4\) in \(H\).
In either situation, the monochromatic subgraph \(G_3 =P_4= (v_3, v_5, v_2, v_4)\) is edge-disjoint from \(A_4\) and \(A_3\) and can be decomposed into \(A_2=2K_2\) and \(A_1= K_2\). Thus, \(s\) is a Ramsey chain in \(G\). \(\square\)
In summary, we have the following.
Theorem 3.11. If \(s\) is a Ramsey chain with target link \(G_4\) with \(R(G_4)= 6\), then \(TR(s)=R(G_4)\).
We now consider Ramsey chains of length 4 whose target link \(G_4\) has Ramsey number 7. Thus, \(G_4\in\{K_{1, 3}+e, K_{1, 4}, K_3+K_2, K_{1, 3}+K_2, 2P_3\}\). We show that if \(R(G_4)= 7\), then \(TR(s)=R(G_4)\). First, we present two lemmas.
Lemma 3.12. If \(G\) is a graph of order \(n\ge 7\) and size \(m \ge 2n\), then every red-blue coloring of \(G\) results in a monochromatic subgraph \(G_3= P_3+K_2\). Consequently, every red-blue coloring of \(G\) results in a monochromatic subgraph \(G_2 \in \{P_3, 2K_2\}\).
Proof. For a graph \(G\) of order \(n\ge 7\) and size \(m \ge 2n\) with a red-blue coloring, let \(G_r\) be the red subgraph and let \(G_b\) be the blue subgraph. We may assume that \(|E(G_r)| \ge |E(G_b)|\). Thus \(G_r\) has order \(n\ge 7\) and size at least \(n\). Since a forest (each component is a tree) of order \(n\) with \(k\ge 1\) components has exactly \(n-k\) edge and \(K_4\) has six edges, it follows that \(G\) is neither a forest nor \(K_4\). In particular, \(G\) is neither a star nor a matching. This implies that \(G_r\) contains \(P_3+K_2\) as a subgraph. Becuase each of \(P_3\) and \(2K_2\) is a subgraph of \(P_3+K_2\), it follows that \(G_r\) contains \(P_3\) or \(2K_2\). \(\square\)
Lemma 3.13. [5] Every red-blue coloring of \(K_7\) results in two edge-disjoint monochromatic triangles.
Theorem 3.14. If \(s\) is a Ramsey chain with target link \(K_{1, 3} + e\), then \(TR(s)=R(K_{1, 3} + e)=7\).
Proof. By Observation 1.3, it suffices to show that \(TR(s)\le 7\). Let \(s= (G_1, G_2, G_3, G_4)\) be a Ramsey chain where \(G_4=K_{1, 3} + e\). Then \(G_3 \in \{K_{1, 3}, P_4, K_3\}\) and \(G_2 \in \{P_3, 2K_2\}\). For a red-blue coloring of \(G=K_7\) with \(V(G)=\{v_1, v_2, \ldots, v_7\}\), we first show that \(G\) contains edge-disjoint monochromatic subgraphs \(G_4 = K_{1, 3} + e\) and \(G_3 \in \{K_{1, 3}, P_4, K_3\}\).
\(\star\) First, suppose that \(G_3 \in \{K_{1, 3}, P_4\}\). Since \(R(K_{1, 3} + e)=7\), there is a monochromatic subgraph \(G_4=K_{1, 3} + e\) with \(E(G_4)=\{v_iv_4: i = 1, 2, 3\}\cup \{v_1v_2\}\), say. Let \(F = G – E(G_4)\). Since at least three of the five edges \(v_6v_i\) (\(1 \le i \le 5\)) of \(F\) have the same color, there is a monochromatic subgraph \(G_3= K_{1, 3}\) in \(F\). Since \(G[\{v_1, v_3, v_5, v_6, v_7\}] \cong K_5 \subseteq F\) and \(R(P_4) = 5\), there is a monochromatic subgraph \(G_3 = P_4\) in \(F\).
\(\star\) Next, suppose that \(G_3=K_3\). By Lemma 3.13, \(G= K_7\) contains two edge-disjoint monochromatic triangles \(T_1\) and \(T_2\). We may assume that either \(V(T_1)=\{v_1, v_2, v_3\}\) and \(V(T_2)=\{v_3, v_4, v_5\}\) or \(V(T_1)=\{v_1, v_2, v_3\}\) and \(V(T_2)=\{v_4, v_5, v_6\}\). If \(T_1\) and \(T_2\) have different colors, then regardless of the color of \(v_1v_3\), there are edge-disjoint monochromatic subgraphs \(G_4 = K_{1, 3} + e\) and \(G_3= K_3\). Thus, we may assume that \(T_1\) and \(T_2\) have the same color, say red. If there is a red edge that joins either (1) a vertex of \(T_1\) and a vertex of \(T_2\) or (2) a vertex of \(V(T_1) \cup V(T_2)\) and the vertex \(v_7\), then there are edge-disjoint red subgraphs \(G_4 = K_{1, 3} + e\) and \(G_3= K_3\). If every edge between \(V(T_1)\) and \(V(T_2)\) and every edge between \(V(T_1)\cup V(T_2)\) and \(v_7\) is blue, then there are edge-disjoint blue subgraphs \(G_4 = K_{1, 3} + e\) and \(G_3= K_3\).
The graph \(H= G- [E(G_4)\cup E(G_3)]\) has order 7 and size 14. By Lemma 3.12, \(H\) contains a monochromatic subgraph \(G_2\in \{P_3, 2K_2\}\). Since the size of \(G\) is 21 and \(|E(G_4)\cup E(G_3)\cup E(G_2)| = 9\), there is an edge in \(E(G)-[E(G_4)\cup E(G_3)\cup E(G_2)]\) that is available for \(G_1= K_2\). Therefore, \(s\) is a Ramsey chain in \(G\). \(\square\)
Theorem 3.15. If \(s\) is a Ramsey chain with target link \(K_3+K_2\), then \(TR(s)=R(K_3+K_2)=7\).
Proof. By Observation 1.3, it suffices to show that \(TR(s)\le 7\). Let \(s= (G_1, G_2, G_3, G_4)\) be a Ramsey chain where \(G_4=K_3+K_2\). Then \(G_3 \in \{K_3, P_3+K_2\}\) and \(G_2 \in \{P_3, 2K_2\}\). Let there be given a red-blue coloring of \(G=K_7\) with \(V(G)=\{v_1, v_2, \ldots, v_7\}\). First, we show that \(G\) contains edge-disjoint monochromatic subgraphs \(G_4 = K_3+K_2\) and \(G_3 \in \{K_3, P_3+K_2\}\).
\(\star\) First, suppose that \(G_3= P_3+K_2\). Since \(R(K_3+K_2)=7\), there is a monochromatic subgraph \(G_4=K_3+K_2\) where \(E(G_4)=\{v_1v_2, v_2v_3, v_3v_1\}\cup \{v_4v_5\}\), say. Since \(F = G – E(G_4)\) is a graph of order 7 and size \({7 \choose 2}-4=17 \ge 14\), it follows by Lemma 3.12 that \(F\) contains a monochromatic subgraph \(G_3=P_3+K_2\).
\(\star\) Next, suppose that \(G_3=K_3\). It follows by Lemma 3.13 that \(G= K_7\) contains two edge-disjoint monochromatic triangles \(T_1\) and \(T_2\). First, suppose that \(T_1\) and \(T_2\) have a vertex \(v_3\) in common, say \(V(T_1)=\{v_1, v_2, v_3\}\) and \(V(T_2)=\{v_3, v_4, v_5\}\). See Figure 6. If \(T_1\) and \(T_2\) are of different colors, then regardless of the color of \(v_6v_7\), there are edge-disjoint monochromatic subgraphs \(G_4 = K_3+K_2\) and \(G_3= K_3\). Thus, we may assume that \(T_1\) and \(T_2\) have the same color, say red. If there is a red edge joining a vertex in \(\{v_6, v_7\}\) and a vertex in \(V(T_1)\cup V(T_2)\), then there are edge-disjoint red subgraphs \(G_4 = K_3+K_2\) and \(G_3= K_3\). Thus, we may assume that every edge joining a vertex in \(\{v_6, v_7\}\) and a vertex in \(V(T_1)\cup V(T_2)\) is blue. Regardless of the color of \(v_6v_7\), there are edge-disjoint monochromatic subgraphs \(G_4 = K_3+K_2\) and \(G_3= K_3\).
Next, suppose that \(T_1\) and \(T_2\) are vertex-disjoint, say \(V(T_1)=\{v_1, v_2, v_3\}\) and \(V(T_2)=\{v_4, v_5, v_6\}\). See Figure 7. If \(T_1\) and \(T_2\) are of different color, say \(T_1\) is red and \(T_2\) is blue, then we may assume that \(v_7v_i\) is red for \(i = 1, 2, 3\) and \(v_7v_j\) is blue for \(j = 4, 5, 6\); for otherwise, there are edge-disjoint monochromatic subgraphs \(G_4 = K_3+K_2\) and \(G_3= K_3\). Then regardless of the color of \(v_1v_4\), there are edge-disjoint monochromatic subgraphs \(G_4 = K_3+K_2\) and \(G_3= K_3\). Thus, we may assume that \(T_1\) and \(T_2\) have the same color, say red. Then \(v_7v_i\) is blue for each integer \(i\) with \(1 \le i \le 6\), for otherwise, there are edge-disjoint red subgraphs \(G_4 = K_3+K_2\) and \(G_3= K_3\). If there is a blue edge joining a vertex of \(T_1\) and a vertex of \(T_2\), say \(v_1v_4\) is blue, then there are a red \(G_4 = K_3+ K_2 = T_1+(v_4, v_5)\) and a blue \(G_3=K_3=(v_1, v_4, v_7, v_1)\). Thus, we may assume that every edge between \(T_1\) and \(T_2\) are red. Then there are edge-disjoint red subgraphs \(G_4 = K_3+K_2\) and \(G_3= K_3\). For example, \(G_4 = K_3+ K_2 = T_1+(v_4, v_5)\) and \(G_3=(v_1, v_5, v_6, v_1)\).
The graph \(H= G- [E(G_4)\cup E(G_3)]\) has order 7 and size 14. By Lemma 3.12, \(H\) contains a monochromatic subgraph \(G_2\in \{P_3, 2K_2\}\). Since the size of \(G\) is 21 and \(|E(G_4)\cup E(G_3)\cup E(G_2)| = 9\), there is an edge in \(E(G)- [E(G_4)\cup E(G_3)\cup E(G_2)]\) that is available for \(G_1= K_2\). Therefore, \(s\) is a Ramsey chain in \(G\). \(\square\)
Theorem 3.16. If \(s\) is a Ramsey chain with target link \(K_{1, 3}+K_2\), then \(TR(s)=R(K_{1, 3}+K_2)=7\).
Proof. By Observation 1.3, it suffices to show that \(TR(s)\le 7\). Let \(s= (G_1, G_2, G_3, G_4)\) be a Ramsey chain where \(G_4=K_{1, 3}+K_2\). Then \(G_3 \in \{K_{1, 3}, P_3+K_2\}\) and \(G_2 \in \{P_3, 2K_2\}\). Let there be given a red-blue coloring of \(G=K_7\) with \(V(G)=\{v_1, v_2, \ldots, v_7\}\). Since \(R(K_{1, 3}+K_2)=7\), there is a monochromatic subgraph \(G_4=K_{1, 3}+K_2\) of \(G\) where \(E(G_4)= \{v_1v_i: i = 2, 3, 4\} \cup \{v_5v_6\}\), say. Let \(F = G – E(G_4)\). Since at least three of the six edges \(v_7v_i\) (\(1 \le i \le 6\)) of \(F\) have the same color, there is a monochromatic subgraph \(G_3 = K_{1, 3}\) in \(F\). Furthermore, since \(F\) has order 7 and size 17, it follows by Lemma 3.12 that \(F\) contains a monochromatic subgraph \(G_3=P_3+K_2\). Next, let \(H= G- [E(G_4)\cup E(G_3)]\). Then \(H\) is a graph of order 7 and size 14. By Lemma 3.12 again, \(H\) contains a monochromatic subgraph \(G_2\in \{P_3, 2K_2\}\). Since the size of \(G\) is 21 and \(|E(G_4)\cup E(G_3)\cup E(G_2)| = 9\), there is an edge in \(E(G)- [E(G_4)\cup E(G_3)\cup E(G_2)]\) that is available for \(G_1= K_2\). Therefore, \(s\) is a Ramsey chain in \(G\). \(\square\)
Theorem 3.17. If \(s\) is a Ramsey chain with target link \(2P_3\), then \(TR(s)=R(2P_3)= 7\).
Proof. By Observation 1.3, it suffices to show that \(TR(s)\le R(2P_3) = 7\). Let \(s= (G_1, G_2, G_3, G_4)\) be a Ramsey chain where \(G_4=2P_3\). Then \(G_3 = P_3+K_2\) and \(G_2 \in \{P_3, 2K_2\}\). Let there be given a red-blue coloring of \(G=K_7\) with \(V(G)=\{v_1, v_2, \ldots, v_7\}\). Since \(R(2P_3)=7\), there is a monochromatic subgraph \(G_4=2P_3\) of \(G\) where \(V(G_4)=\{v_i: 1\le i \le 6\}\), say. Let \(F = G – E(G_4)\). Since \(F\) has order 7 and size 17, it follows by Lemma 3.12 that \(F\) contains a monochromatic subgraph \(G_3=P_3+K_2\). The graph \(H= G- [E(G_4)\cup E(G_3)]\) has order 7 and size 14. By Lemma 3.12 again, \(H\) contains a monochromatic subgraph \(G_2\in \{P_3, 2K_2\}\). Since the size of \(G\) is 21 and \(|E(G_4)\cup E(G_3)\cup E(G_2)| = 9\), there is an edge in \(E(G)- [E(G_4)\cup E(G_3)\cup E(G_2)]\) that is available for \(G_1= K_2\). Therefore, \(s\) is a Ramsey chain in \(G\). \(\square\)
In summary, we then have the following.
Theorem 3.18. If \(s\) is a Ramsey chain with target link \(G_4\) with \(R(G_4)= 7\), then \(TR(s)=R(G_4)\).
Finally, we consider Ramsey chains whose target link \(G_4 \in \{P_4+K_2, P_3+2K_2\}\) has Ramsey number 8 or 9. We show here that \(TR(s)=R(G_4)\) for every such Ramsey chain \(s\), beginning with \(G_4 = P_4+K_2\).
Theorem 3.19. If \(s\) is a Ramsey chain with target link \(P_4 + K_2\), then \(TR(s)=R(P_4 + K_2)=8\).
Proof. By Observation 1.3, it suffices to show that \(TR(s)\le 8\). Let \(s= (G_1, G_2, G_3, G_4)\) be a Ramsey chain where \(G_4=P_4 + K_2\). Then \(G_3 \in \{P_4, P_3+ K_2\}\) and \(G_2 \in \{P_3, 2K_2\}\). Let there be given a red-blue coloring of \(G=K_8\) with \(V(G)=\{v_1, v_2, \ldots, v_8\}\). Since \(R(P_4 + K_2)=8\), there is a monochromatic subgraph \(G_4=P_4 + K_2\) of \(G\) where \(G_4=(v_1, v_2, v_3, v_4) + (v_5, v_6)\), say.
Let \(F = G – E(G_4)\). Since \(F\) has order 8 and size \({8 \choose 2}-4= 24 > 16\), it follows by Lemma 3.12 that \(F\) contains a monochromatic subgraph \(G_3=P_3+K_2\). Furthermore, \(G[\{v_1, v_3, v_5, v_7, v_8\}]=K_5 \subseteq F\). Since \(R(P_4) = 5\), there is a monochromatic subgraph \(G_3=P_4\). Next, the graph \(H= G- [E(G_4)\cup E(G_3)]\) has order 8 and size 21. By Lemma 3.12 again, \(H\) contains a monochromatic subgraph \(G_2\in \{P_3, 2K_2\}\). Furthermore, \(H\) contains an edge not in \(G_2\) that is available for \(G_1= K_2\). Therefore, \(s\) is a Ramsey chain in \(G\). \(\square\)
To show that \(TR(s)=R(G_4)\) for every such Ramsey chain \(s\) with target link \(P_3 + 2K_2\), we first present a lemma.
Lemma 3.20. [16] Every red-blue coloring of \(K_8\) produces four pairwise edge-disjoint monochromatic copies of \(3K_2\).
Theorem 3.21. If \(s\) is a Ramsey chain with target link \(P_3 + 2K_2\), then \(TR(s)=R(P_3 +2 K_2)=9\).
Proof. By Observation 1.3, it suffices to show that \(TR(s)\le 9\). Let \(s= (G_1, G_2, G_3, G_4)\) be a Ramsey chain where \(G_4=P_3 + 2K_2\). Then \(G_3 \in \{P_3+ K_2, 3K_2\}\) and \(G_2 \in \{P_3, 2K_2\}\). Let there be given a red-blue coloring of \(G=K_9\) with \(V(G)=\{v_1, v_2, \ldots, v_9\}\). We show that \(G\) contains edge-disjoint monochromatic subgraphs \(G_4 = P_3 + 2K_2\) and \(G_3 \in \{P_3+ K_2, 3K_2\}\).
\(\star\) First, suppose that \(G_3 = P_3+K_2\). Since \(R(P_3 +2 K_2)=9\), there is a monochromatic subgraph \(G_4 = P_3 + 2K_2\). Furthermore, since \(G – E(G_4)\) has order 9 and size \({9 \choose 2}-4= 32 > 18\), it follows by Lemma 3.12 that \(G – E(G_4)\) contains a monochromatic subgraph \(G_3=P_3+K_2\).
\(\star\) Next, suppose that \(G_3 =3K_2\). Let \(F = G-v_9 \cong K_8\). By Lemma 3.20, \(F\) contains four pairwise edge-disjoint monochromatic copies \(F_1, F_2, F_3, F_4\) of \(3K_2\). If three of the subgraphs \(F_1, F_2, F_3, F_4\) have the same color, say \(F_1\), \(F_2\), \(F_3\) are red \(3K_2\), then there is a red \(G_4 = P_3+2K_2\) in the subgraph \(G[E(F_1)\cup E(F_2) \cup E(F_3)]\) induced by \(E(F_1)\cup E(F_2) \cup E(F_3)\). Let \(G_3 = F_4 = 3K_2\). Thus, we may assume that \(F_1\) and \(F_2\) are red and \(F_3\) and \(F_4\) are blue. Let \(A = G[E(F_1)\cup E(F_2)]\) and \(B= G[E(F_3)\cup E(F_4)]\). If \(A\ne C_6\) or \(B\ne C_6\), then there is a red \(G_4 = P_3+2K_2\) in \(A\) or \(B\). Thus, we may assume that\(A= C_6\) is red and \(B= C_6\) is blue. If \(v_9\) is joined to a vertex in \(A\) by a red edge, then there is a red \(G_4 = P_3+2K_2\). Let \(G_3= F_3= 3K_2\) in \(F\). Thus, we may assume that \(v_9\) is joined to every vertex in \(A\) by a blue edge. Since \(V(A) \cap V(B) \ne \emptyset\), it follows that \(v_9\) is joined to a vertex in \(B\) by a blue edge, producing a blue \(G_4 = P_3+2K_2\). Let \(G_3= F_1= 3K_2\) in \(F\).
The graph \(H= G- [E(G_4)\cup E(G_3)]\) has order 9 and size 29. By Lemma 3.12, \(H\) contains a monochromatic subgraph \(G_2\in \{P_3, 2K_2\}\). Furthermore, \(H\) contains an edge not in \(G_2\) that is available for \(G_1= K_2\). Therefore, \(s\) is a Ramsey chain in \(G\). \(\square\)
In summary, we have the following result.
Theorem 3.22. If \(s\) is a Ramsey chain with target link \(G_4\) where \(R(G_4)= 8\) or \(R(G_4)= 9\), then \(TR(s)=R(G_4)\).
We have seen several graphs \(H\) for which if \(s\) is a Ramsey chain with target link \(H\), then \(TR(s) = R(H)\). In particular, all graphs \(H\) of size 3 or 4 without isolated vertices have the property that \(TR(s) = R(H)\) for every Ramsey chain \(s\) with target link \(H\). In fact, it can be verified that there are other well-known graphs with this property. For example, if \(H \in \{K_4, C_5, P_6\}\), then \(TR(s) = R(H)\) for every Ramsey chain \(s\) with target link \(H\). Furthermore, we know of no graph \(H\) and a Ramsey chain \(s\) with target link \(H\) such that \(TR(s) > R(H)\). Therefore, we close with the following question.
Question 4.1. Is there a graph \(H\) without isolated vertices and a Ramsey chain \(s\) with target link \(H\) for which \(TR(s) > R(H)\)?