For a graph \(F\) and a positive integer \(t\), the vertex-disjoint Ramsey number \(VR_t(F)\) is the minimum positive integer \(n\) such that every red-blue coloring of the edges of the complete graph \(K_n\) of order \(n\) results in \(t\) pairwise vertex-disjoint monochromatic copies of subgraphs isomorphic to \(F\), while the edge-disjoint Ramsey number \(ER_t(F)\) is the corresponding number for edge-disjoint subgraphs. These numbers have been investigated for the three connected graphs \(K_3\), \(P_4\) and \(K_{1, 3}\) of size 3. For two vertex-disjoint graphs \(G\) and \(H\), let \(G+H\) denote the union of \(G\) and \(H\). Here we study these numbers for the two disconnected graphs \(3K_2\) and \(P_3+P_2\) of size 3. It is shown that \(VR_t(3K_2)= 6t+2\) and \(VR_t(P_3+P_2)= 5t+1\) for every positive integer \(t\). The numbers \(ER_t(3K_2)\) and \(ER_t(P_3+P_2)\) are determined for \(t \le 4\) and bounds are established for \(ER_t(3K_2)\) and \(ER_t(P_3+P_2)\) when \(t \ge 5\). Other results and problems are presented as well.
In a red-blue coloring of a graph \(G\), every edge of \(G\) is colored red or blue. For two graphs \(F\) and \(H\), the well-known Ramsey number \(R(F, 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\)). Therefore, for a single graph \(F\), the Ramsey number \(R(F, F)\), also denoted by \(R(F)\), is the minimum positive integer \(n\) such that for every red-blue coloring of \(K_n\), there is a subgraph of \(K_n\) isomorphic to \(F\) all of whose edges are colored the same (a monochromatic \(F\)). While these numbers exist for every graph \(F\) (see [8]), it is challenging in general to determine the exact value \(R(F)\) for many graphs \(F\). For example, \(R(K_n)\) is only known when \(n \le 4\) (see [2, 6]).
Perhaps the best known Ramsey number is \(R(K_3)\) which is \(6\). This result was established by Greenwood and Gleason [6] in 1955. In fact, this result essentially appeared as Problem A2 in the 1953 William Lowell Putnam Exam (see [6]). While every red-blue coloring of \(K_6\) always results in a monochromatic triangle \(K_3\), it turns out that every red-blue coloring of \(K_6\) always results in at least two monochromatic triangles (see [5]). However, it is not true that every red-blue coloring of \(K_6\) always results in two edge-disjoint monochromatic triangles. For example, in the red-blue coloring of \(K_6\) in Figure 1 (where a bold edge represents a red edge and a thin edge represents a blue edge), there do not exist two edge-disjoint monochromatic triangles.
On the other hand, every red-blue coloring of \(K_7\) always results in two edge-disjoint monochromatic triangles.
Proposition 1.1. [1] Every red-blue coloring of \(K_7\) results in two edge-disjoint monochromatic triangles.
While every red-blue coloring of \(K_7\) results in two edge-disjoint monochromatic triangles, it is not true that every red-blue coloring of \(K_7\) always results in two vertex-disjoint monochromatic triangles. For example, the red-blue coloring of \(K_7\) of Figure 2 with red subgraph \(K_5+K_2\) and blue subgraph \(K_{2, 5}\) does not contain two vertex-disjoint monochromatic copies of \(K_3\). However, every red-blue coloring of \(K_8\) results in two vertex-disjoint monochromatic triangles.
Proposition 1.2. [1] Every red-blue coloring of \(K_8\) results in two vertex-disjoint monochromatic triangles.
Consequently, 6 is the smallest order \(n\) of a complete graph \(K_n\) for which every red-blue coloring results in a monochromatic triangle, 7 is the smallest order \(n\) of a complete graph \(K_n\) for which every red-blue coloring results in two edge-disjoint monochromatic triangles, and 8 is the smallest order \(n\) of a complete graph \(K_n\) for which every red-blue coloring results in two vertex-disjoint monochromatic triangles. These facts gave rise to the idea of extending Ramsey numbers to multiple Ramsey numbers in [1].
Let \(t\) be a positive integer and \(F\) a graph without isolated vertices. The vertex-disjoint Ramsey number \(VR_t(F)\) is the minimum positive integer \(n\) such that for every red-blue coloring of \(K_n\), there are at least \(t\) pairwise vertex-disjoint monochromatic copies of \(F\). Thus, \(VR_1(F) = R(F)\) for every graph \(F\). Since the Ramsey number \(R(tF)\) exists for the union \(tF\) of \(t\) pairwise vertex-disjoint copies of a graph \(F\) by a result of Ramsey [8], we have the following.
Observation 1.3. [1] For every graph \(F\) without isolated vertices and every positive integer \(t\), the number \(VR_t(F)\) exists and \(t|V(F)| \le VR_t(F) \le R(tF)\). Furthermore, \(VR_t(F) \le VR_{t+1}(F)\).
Let \(t\) be a positive integer and let \(F\) be a graph without isolated vertices. The edge-disjoint Ramsey number \(ER_t(F)\) of \(F\) is the minimum positive integer \(n\) such that for every red-blue coloring of \(K_n\), there are at least \(t\) pairwise edge-disjoint monochromatic copies of \(F\). Thus, \(ER_1(F) = R(F)\) for every graph \(F\).
Observation 1.4. [1] For every graph \(F\) without isolated vertices and every positive integer \(t\), the number \(ER_t(F)\) exists and \(ER_t(F) \le VR_t(F)\). Furthermore, \(ER_t(F) \le ER_{t+1}(F)\).
The concepts of vertex-disjoint and edge-disjoint Ramsey numbers of graphs were introduced and studied in [1] and studied further in [7]. In [1], the numbers \(VR_t(F)\) and \(ER_t(F)\) were investigated for the two connected graphs of order 3, namely \(K_3\) and \(P_3\). The following two results were obtained on vertex-disjoint Ramsey numbers of these two graphs.
Theorem 1.5. [1] For an integer \(t \ge 2\), \(VR_{t} (K_3)= 3t+2\).
Theorem 1.6. [1] For every positive integer \(t\), \(VR_{t}(P_3)= 3t\).
Regarding edge-disjoint Ramsey numbers of \(K_3\), it was also shown in [1] that \(ER_2(K_3) = 7\), \(ER_3(K_3) = 9\), and \(ER_4(K_3) = 10\). The edge-disjoint Ramsey numbers of \(P_3\) were obtained in [1] as well.
Theorem 1.7. [1] For every positive integer \(t\), \(ER_t(P_3)= \lceil 2 \sqrt{t} + 1 \rceil\).
In [7], the numbers \(VR_t(F)\) and \(ER_t(F)\) were investigated for the connected graphs \(F\) of size 3 different from \(K_3\), namely the star \(K_{1, 3}\) and the path \(P_4\) of order 4. The following two results were obtained on vertex-disjoint Ramsey numbers of these two graphs.
Theorem 1.8. [7] For each positive integer \(t\), \(VR_{t}(P_4) = 4t+1\).
Theorem 1.9. [7] \(VR_1(K_{1, 3})= R(K_{1, 3}) = 6\) and for each integer \(t\ge 2\), \(VR_t(K_{1, 3}) = 4t\).
It was also shown in [7] that \(ER_2(K_{1, 3})=6\) and \(ER_t(K_{1, 3})=7\) for \(t = 3, 4\), while \(ER_t(P_4) = t+3\) for \(2 \le t \le 5\). Upper and lower bounds for these two numbers were established in [7] as well.
Theorem 1.10. [7] For each integer \(t \ge 4\), \(\left\lceil \frac{3 + \sqrt{9+24t}}{2}\right\rceil \le ER_t(K_{1, 3}) \le t+3.\)
Theorem 1.11. [7] For each integer \(t \ge 2\), \(ER_t(P_4) \le t+3\).
(1) If \(ER_t(P_4)\not\equiv 0 \pmod 3\), then \(ER_t(P_4) \ge \left\lceil \frac{3 + \sqrt{1+24t}}{2}\right\rceil\).
(2) If \(ER_t(P_4)\equiv 0 \pmod 3\), then \(ER_t(P_4) \ge \left\lceil \frac{3 + \sqrt{9+24t}}{2}\right\rceil\).
For two vertex-disjoint graphs \(G\) and \(H\), let \(G+H\) denote the union of \(G\) and \(H\) with \(V(G+H) = V(G) \cup V(H)\) and \(E(G+H) = E(G) \cup E(H)\). The Cartesian product of \(G\) and \(H\) is denoted by \(G \ \Box \ H\) with \(V(G \ \Box \ H) = V(G) \times V(H)\) where two distinct vertices \((u, v)\) and \((x, y)\) are adjacent in \(G \ \Box \ H\) if either \(u = x\) and \(vy \in E(H)\) or \(v = y\) and \(ux \in E(G)\). We refer to the book [2] for notation and terminology not defined here. The goal of this paper is to study \(VR_t(F)\) and \(ER_t(F)\) for the two disconnected connected graphs \(F\) of size 3, namely the matching \(3K_2\) and the union \(P_3+P_2\) of \(P_3\) and \(P_2\).
We begin with the vertex-disjoint Ramsey numbers of the matching \(3K_2\) of size 3. An upper bound for \(VR_t(F)\) was established in [7] for every graph \(F\) of order at least 4 with no isolated vertices.
Proposition 2.1. [7] Let \(F\) be a graph of order \(n \ge 4\) without isolated vertices. If there is a positive integer \(t_0\) such that \(VR_{t_0}(F) \le q\), then \(VR_{t}(F) \le q + (t-t_0)n\) for every integer \(t \ge t_0\).
With the aid of Proposition 2.1, we are able to determine \(VR_t(3K_2)\) for every positive integer \(t\).
Theorem 2.2. For each positive integer \(t\), \(VR_{t}(3K_2) = 6t+2\).
Proof. Since \(VR_1(3K_2) =R(3K_2)= 8\) and the order of \(3K_2\) is 6, it follows by Proposition 2.1 that \(VR_{t}(3K_2) \le 8+6(t-1)= 6t+2\). Next, consider the red-blue coloring of \(G = K_{6t+1}\) with red subgraph \(G_r=K_2 \vee \overline{K_{6t-1}}\) (the join of \(K_2\) and the empty graph \(\overline{K_{6t-1}}\) of order \(6t-1\)) and blue subgraph \(G_b = K_{6t-1}\). Since the edge-independence number of \(G_r\) is \(\alpha'(G_r)=2\), there is no red \(3K_2\) in \(G_r\). The blue subgraph \(G_b\) has order \(6t-1\) and so there are no \(t\) pairwise vertex-disjoint blue copies of \(3K_2\). Since this red-blue coloring fails to have \(t\) pairwise vertex-disjoint monochromatic copies of \(3K_2\), it follows that \(VR_t(3K_2) \ge 6t+2\) and so \(VR_t(3K_2)=6t+2\). ◻
For the edge-disjoint Ramsey number \(ER_t(3K_2)\), we begin by determining \(ER_t(3K_2)\) for small values of \(t\), namely \(1\le t \le 4\). First, we provide some preliminary information. The following two results are known.
Thus, \(ER_1(3K_2) = R(3K_2) = 8\) by Theorem 2.3.
Theorem 2.4. [2] For every integer \(k \ge 1\), the complete graph \(K_{2k}\) can be factored into \(k-1\) Hamiltonian cycles and a \(1\)-factor.
The matching (or edge-independence) number \(\alpha'(G)\) of a graph \(G\) is the maximum number of edges in \(G\), no two of which are adjacent. In order to determine \(ER_t(3K_2)\) for \(2 \le t \le 4\), the following lemma will be useful.
Lemma 2.5. If \(G\) is a graph of order \(8\) and size \(10\) or more, then either \[\alpha'(G) \ge 3, \quad G\in \{K_5 + \overline{K}_3, \ (K_3+\overline{K_4}) \vee K_1\},\text{ or }G \subseteq K_2\vee\overline{K}_6.\]
Proof. Let \(P=(v_0, v_1, \ldots, v_k)\) be a path of greatest length \(k\) in the graph \(G\). If \(k \ge 5\), then {\(v_0v_1\), \(v_2v_3\), \(v_4v_5\)} is an independent set of three edges in \(G\) and thus \(\alpha'(G) \ge 3\). Hence, we may assume that \(2 \le k \le 4\). We consider three cases according to the value of \(k\).
Case 1. \(k = 2\). Thus, every nonempty component of \(G\) is either \(K_3\) or a star. Therefore, \(|E(G)| \le 7\), a contradiction.
Case 2. \(k = 3\). Thus, \(P=(v_0, v_1, v_2, v_3)\) is a path of greatest length 3 in \(G\). Let \(v_4, v_5, v_6, v_7\) be the remaining vertices of \(G\). Then \(v_0v_i, v_3v_i \notin E(G)\) for \(i = 4, 5, 6, 7\), for otherwise \(G\) contains a path of length 4 or more. If any two of the four vertices \(v_4, v_5, v_6, v_7\) are adjacent, then \(\alpha'(G) \ge 3\). Therefore, we may assume that \(\{v_4, v_5, v_6, v_7\}\) is an independent set of vertices in \(G\). Let \(F\) be the bipartite graph with partite sets \(\{v_0, v_1, v_2, v_3\}\) and \(\{v_4, v_5, v_6, v_7\}\). Then \(|E(F)| \le 8\). Let \(H=G[\{v_0, v_1, v_2, v_3\}]\) be the subgraph induced by \(\{v_0, v_1,v_2, v_3\}\) in \(G\). Then \(E(G)=E(F)\cup E(H)\), see Figure 3.
If \(H\) is a Hamiltonian subgraph of \(G\), then no vertex of \(H\) is adjacent to any vertex in {\(v_4\), \(v_5\), \(v_6\), \(v_7\)}, for otherwise \(G\) contains a path of length 4 or more. Therefore, if \(H\) is Hamiltonian, then \(|E(G)|=|E(H)| \le 6\), a contradiction. Thus, we may assume that \(H\) is not Hamiltonian. Thus, \(v_0v_3 \notin E(H)\) and at most one of \(v_0v_2\) and \(v_1v_3\) is an edge of \(H\). Therefore, \(|E(H)|\le 4\). If both \(v_1\) and \(v_2\) are adjacent to a vertex \(v_i\) where \(4 \le i \le 7\), then \(G\) contains a path of length 4, a contradiction. Thus, \(|E(F)| \le 4\) and so \(|E(G)|=|E(H)|+ |E(F)|\le 4+4= 8\), a contradiction.
Case 3. \(k = 4\). Thus, \(P=(v_0, v_1, v_2, v_3, v_4)\) is a path of greatest length 4 in \(G\). Let \(v_5, v_6, v_7\) be the remaining vertices of \(G\). Then \(v_0v_i, v_4v_i \notin E(G)\) for \(i = 5, 6, 7\), for otherwise \(G\) contains a path of length 5 or more. If any two of the four vertices \(v_2, v_5, v_6, v_7\) are adjacent, then \(\alpha'(G) \ge 3\). Therefore, we may assume that \(\{v_2, v_5, v_6, v_7\}\) is an independent set of vertices in \(G\). Let \(F\) be the bipartite graph with partite sets \(\{v_0, v_1, \ldots, v_4\}\) and \(\{v_5, v_6, v_7\}\). Then \(|E(F)| \le 6\). Let \(H=G[\{v_0, v_1, \ldots, v_4\}]\) be the subgraph induced by \(\{v_0, v_1, \ldots, v_4\}\) in \(G\). Then \(E(G)=E(F)\cup E(H)\), see Figure 4.
If \(H\) is a Hamiltonian subgraph of \(G\), then no vertex of \(H\) is adjacent to any vertex in {\(v_5\), \(v_6\), \(v_7\)}, for otherwise \(G\) contains a path of length 5 or more. Therefore, if \(H\) is Hamiltonian, then \(|E(G)|=|E(H)| \le 10\). Since \(|E(G)|\ge 10\), it follows that \(|E(G)|= 10\) and \(G=K_5 +\overline{K}_3\) in which \(G[\{v_0, v_1, \ldots, v_4\}]=K_5\) and \(G[\{v_5, v_6, v_7\}]=\overline{K}_3\). Thus, we may assume that \(H\) is not Hamiltonian and so \(v_0v_4 \notin E(G)\).
\(\star\) First, suppose that both \(v_0v_2\) and \(v_2v_4\) belong to \(G\). Then \(v_1v_4, v_0v_3 \notin E(H)\) since \(H\) is not Hamiltonian and \(v_1v_i, v_4v_i \notin E(G)\) for \(i = 5, 6, 7\), for otherwise \(\alpha'(G) \ge 3\). Thus, \(|E(G)| \le 7\), a contradiction.
\(\star\) Next suppose that exactly one of \(v_0v_2\) and \(v_2v_4\) belongs to \(G\), say \(v_0v_2\in E(G)\) and \(v_2v_4 \notin E(G)\). Then \(v_1v_4 \notin E(H)\) (since \(H\) is not Hamiltonian) and \(v_1v_i \notin E(G)\) for \(i = 5, 6, 7\), for otherwise \(\alpha'(G) \ge 3\). Thus, \(|E(G)| \le |E(H)|+|E(F)| \le 7+3 =10\). Since \(|E(G)| \ge 10\), it follows that \(|E(G)|= 10\) and so \(v_1v_3 \in E(H)\) and \(G= (K_3+\overline{K}_4) \vee K_1\) where \(G[\{v_0, v_1, v_2\}]=K_3\), \(G[v_4, v_5, v_6, v_7\}]=\overline{K}_4\), and \(\deg_G v_3=7\).
\(\star\) Finally, suppose that \(v_0v_2, v_2v_4 \notin E(G)\). Thus, the edge \(v_1v_3\) may or may not belong to \(G\). Then \(G\) is a subgraph of \(K_2\vee \overline{K}_6\) where \(G[\{v_1, v_3\}]=K_2\) and \(G[\{v_0, v_2, v_4, v_5, v_6, v_7\}]\\=\overline{K}_6\).
Therefore, either \(\alpha'(G) \ge 3\), or \(G\in \{K_5 + \overline{K}_3, (K_3+\overline{K_4}) \vee K_1\}\), or \(G \subseteq K_2\vee\overline{K}_6\). ◻
Theorem 2.6. For \(1 \le t \le 4\), \(ER_t(3K_2)=8\).
Proof. Since \(R(3K_2) = 8\) by Theorem 2.3, we may assume that \(2\le t \le 4\). First, we show that \(ER_2(3K_2) = 8\). Since \(ER_2(3K_2) \ge R(3K_2) =8\), it remains to show that that \(ER_2(3K_2) \le 8\). Let \(c\) be a red-blue coloring of \(G = K_8\). Since \(R(3K_2) =8\), there is a monochromatic subgraph \(F=3K_2\) of \(G\). Let \(H = G-E(F)\). Then \(H\) has order 8 and size \({8 \choose 2}-3= 25\). Let \(H_r\) and \(H_b\) be the red and blue subgraphs of \(H\) having sizes \(m_r\) and \(m_b\) respectively. We may assume that \(m_r \ge m_b\). Thus, \(m_r \ge 13\). Since \(H_r\) has order 8 and size 13 or greater, it follows by Lemma 2.5 that either \(\alpha'(H_r) \ge 3\) or \(H_r=K_2\vee\overline{K}_6\), which contains no \(3K_2\). If \(\alpha'(H_r) \ge 3\), then \(H_r\) contains a subgraph isomorphic to \(3K_2\) which is edge-disjoint from \(F\). Thus, we may assume that \(H_r=K_2\vee\overline{K}_6\). Since the complement of \(H_r\) is \(\overline{H}_r = K_6+\overline{K}_2\), it follows that \(H_b = (K_6+\overline{K}_2)-E(F)\) where \(F= 3K_2\) is a matching of size 3 in \(K_6\). By Theorem 2.4, \(H_b\) is \(3K_2\)-decomposable into four copies of \(3K_2\). Therefore, \(G\) contains two edge-disjoint copies of \(3K_2\) and so \(ER_2(3K_2) \le 8\). Therefore, \(ER_2(3K_2) = 8\).
Next, we show that \(ER_3(3K_2) = 8\). Since \(ER_3(3K_2) \ge ER_2(3K_2) =8\), it remains to show that that \(ER_3(3K_2) \le 8\). Let there be given a red-blue coloring of \(G = K_8\). Since \(ER_2(3K_2) =8\), there are two edge-disjoint monochromatic copies \(F_1\) and \(F_2\) of \(3K_2\). Let \(H = G-[E(F_1)\cup E(F_2)]\). Then \(H\) has order 8 and size \({8 \choose 2}-6= 22\). Let \(H_r\) and \(H_b\) be the red and blue subgraphs of \(H\) having sizes \(m_r\) and \(m_b\), respectively. We may assume that \(m_r \ge m_b\). Thus, \(m_r \ge 11\). Since \(H_r\) has order 8 and size 11 or greater, it follows by Lemma 2.5 that either \(\alpha'(H_r) \ge 3\) or \(H_r\) is a subgraph of \(K_2\vee\overline{K}_6\), which contains no \(3K_2\). If \(\alpha'(H_r) \ge 3\), then \(H_r\) contains a subgraph isomorphic to \(3K_2\) which is edge-disjoint from \(F_1\) and \(F_2\). Thus, we may assume that \(H_r \subseteq K_2 \vee\overline{K}_6\), which contains no \(3K_2\). Since the complement of \(K_2\vee\overline{K}_6\) is \(K_6+\overline{K}_2\), it follows that \(K_6+\overline{K}_2 \subseteq \overline{H}_r\). Consequently, \[H'= (K_6+\overline{K}_2) -[E(F_1)\cup E(F_2)] \subseteq \overline{H}_r – [E(F_1)\cup E(F_2)]\subseteq H_b.\]
While it is possible that \(E(F_1)\not\subseteq E(K_6+\overline{K}_2)\) or \(E(F_2)\not\subseteq E(K_6+\overline{K}_2)\), if \(E(F_1)\cup E(F_2) \subseteq E(K_6+\overline{K}_2)\), then \((K_6+\overline{K}_2) -[E(F_1)\cup E(F_2)] = K_3 \ \Box \ K_2\). Therefore, \(K_3 \ \Box \ K_2 \subseteq H' \subseteq H_b\). Hence, \(H'\) contains a monochromatic copy of \(3K_2\) edge-disjoint from \(F_1\) and \(F_2\). Therefore, \(ER_3(3K_2) \le 8\) and so \(ER_3(3K_2) = 8\).
Finally, we show that \(ER_4(3K_2)=8\). Since \(ER_4(3K_2) \ge ER_3(3K_2) =8\), it remains to show that that \(ER_4(3K_2) \le 8\). Let there be given a red-blue coloring of \(G = K_8\). Let \(G_r\) and \(G_b\) be the red and blue subgraphs of \(G\), respectively. Since \(ER_3(3K_2) =8\), there are three pairwise edge-disjoint monochromatic copies \(F_1, F_2, F_3\) of \(3K_2\). Let \(H = G-[E(F_1)\cup E(F_2)\cup E(F_3)]\). Then \(H\) has order 8 and size \({8 \choose 2}-9= 19\). Let \(H_r\) and \(H_b\) be the red and blue subgraphs of \(H\) having sizes \(m_r\) and \(m_b\), respectively. We may assume that \(m_r \ge m_b\). Thus, \(m_r \ge 10\). Since \(H_r\) has order 8 and size 10 or greater, it follows by Lemma 2.5 that either \(\alpha'(H_r) \ge 3\), \(H_r \in \{K_5 + \overline{K}_3, \ (K_3+\overline{K_4}) \vee K_1\}\), or \(H_r\) is a subgraph of \(K_2\vee\overline{K}_6\). If \(\alpha'(H_r) \ge 3\), then \(H_r\) contains a subgraph isomorphic to \(3K_2\) which is edge-disjoint from \(F_1, F_2, F_3\). Thus, we may assume that either \(H_r \in \{K_5 + \overline{K}_3, \ (K_3+\overline{K_4}) \vee K_1\}\) or \(H_r\) is a subgraph of \(K_2\vee\overline{K}_6\). We consider these three cases.
Case 1. \(H_r = K_5 + \overline{K}_3\). Then \(\overline{H}_r=K_3\vee \overline{K}_5\). If all subgraphs \(F_1, F_2, F_3\) are blue, then \(G_r = H_r\) and \(G_b=\overline{H}_r=K_3\vee \overline{K}_5\). Since the blue subgraph \(G_b=K_3\vee \overline{K}_5\) contains five pairwise edge-disjoint copies \(F_1', F_2', F_3', F_4', F_5'\) of \(3K_2\), it follows that \(F_1', F_2', F_3', F_4'\) are four pairwise edge-disjoint blue copies of \(3K_2\) in \(G_b\) (and in \(G\)). Thus, we may assume that at least one of \(F_1, F_2, F_3\) is red, say \(F_1\) is red. Let \(J_r = G[E(H_r)\cup E(F_1)]\). Then \(J_r\subseteq G_r\) is a red subgraph of \(G\) and \(E(J_r) \cap [E(F_2)\cup E(F_3)]=\emptyset\). We may assume that \(V(G)=\{v_1, v_2, \ldots, v_8\}\), the vertex set of \(K_5\) in \(H_r\) is \(\{v_1, v_2, v_3, v_4, v_5\}\), and \(E(F_1)=\{v_1v_6, v_2v_7, v_3v_8\}\). Then \(J_r\) contains three pairwise edge-disjoint copies \(F_1^*, F_2^*, F_3^*\) of \(3K_2\) that are edge-disjoint from \(F_2\) and \(F_3\). Thus, \(G\) contains four pairwise edge-disjoint monochromatic copies of \(3K_2\). For example, \(F_1^*, F_2^*, F_3^*, F_2\) are four pairwise edge-disjoint monochromatic copies of \(3K_2\) in \(G\).
Case 2. \(H_r = (K_3+\overline{K_4}) \vee K_1\). Then \(\overline{H}_r=(K_4\vee \overline{K}_3)+ K_1\). If all subgraphs \(F_1, F_2, F_3\) are blue, then \(G_r = H_r\) and \(G_b=\overline{H}_r=(K_4\vee \overline{K}_3)+ K_1\). Since the subgraph \(K_4\vee \overline{K}_3\) of \(G_b\) contains four pairwise edge-disjoint copies \(F_1', F_2', F_3', F_4'\) of \(3K_2\), it follows that \(F_1', F_2', F_3', F_4'\) are four pairwise edge-disjoint blue copies of \(3K_2\) in \(G_b\) (and in \(G\)). Thus, we may assume that at least one of \(F_1, F_2, F_3\) is red, say \(F_1\) is red. Let \(J_r = G[E(H_r)\cup E(F_1)]\). Then \(J_r\subseteq G_r\) is a red subgraph of \(G\) and \(E(J_r) \cap [E(F_2)\cup E(F_3)]=\emptyset\). Furthermore, \(J_r\) is isomorphic to one of the two graphs in Figure 5 where the three dashed edges belong to \(F_1\) in each graph. In either case, \(J_r\) contains three pairwise edge-disjoint copies \(F_1^*, F_2^*, F_3^*\) of \(3K_2\) that are edge-disjoint from \(F_2\) and \(F_3\). Thus, \(G\) contains four pairwise edge-disjoint monochromatic copies of \(3K_2\). For example, \(F_1^*, F_2^*, F_2, F_3\) are four pairwise edge-disjoint monochromatic copies of \(3K_2\) in \(G\).
Case 3. \(H_r\subseteq K_2\vee\overline{K}_6\). We may assume that \(V(\overline{K_6})=\{v_1, v_2, \ldots, v_6\}\) and \(V(K_2)=\{v_7, v_8\}\). Then \(\overline{K_2\vee\overline{K}_6}= K_6 + \overline{K}_2\subseteq \overline{H}_r\), where \(K_6=G[\{v_1, v_2, \ldots, v_6\}]\) and \(V(\overline{K}_2)=\{v_7, v_8\}\). We consider two subcases.
Subcase 3.1. All copies of \(F_1, F_2, F_3\) of \(3K_2\) are blue. Then \(G_r = H_r\) and \(G_b=\overline{H}_r\). Since \(H_r\subseteq K_2\vee\overline{K}_6\), it follows that \(K_6 + \overline{K}_2\subseteq \overline{H}_r = G_b\). The subgraph \(K_6\) of \(G_b\) contains four pairwise edge-disjoint copies \(F_1', F_2', F_3', F_4'\) of \(3K_2\) and so \(F_1', F_2', F_3', F_4'\) are four pairwise edge-disjoint blue copies of \(3K_2\) in \(G_b\) (and in \(G\)).
Subcase 3.2. At least one of \(F_1, F_2, F_3\), say \(F_1\), is red. Since \[E(G)=E(H_r)\cup E(H_b) \cup E(F_1)\cup E(F_2) \cup E(F_3),\] it follows that \(E(\overline{H}_r) = E(H_b) \cup E(F_1)\cup E(F_2) \cup E(F_3)\). Since \(K_6 + \overline{K}_2\subseteq \overline{H}_r\), it follows that \[H' = (K_6 + \overline{K}_2)- [E(F_1)\cup E(F_2) \cup E(F_3)] \subseteq H_b.\]
Thus, \(H'\) contains a \(2\)-regular graph of order 6 (since \(F_i\) may not belong to \(K_6 + \overline{K}_2\) for some \(i = 1, 2, 3\)). If \(H'\) has a copy \(F_4\) of \(3K_2\), then \(F_4\) is a blue \(3K_2\) that is edge-disjoint from \(F_1, F_2, F_3\). Therefore, \(F_1, F_2, F_3, F_4\) are four pairwise edge-disjoint blue copies of \(3K_2\) in \(G\). Thus, we may assume that \(H'\) does not have a copy of \(3K_2\). This implies that \(H'=2K_3\) and \(E(F_1)\cup E(F_2) \cup E(F_3) \subseteq E(K_6)\). Hence, \(E(K_6)=E(H') \cup E(F_1)\cup E(F_2) \cup E(F_3)\) where \(V(K_6)=\{v_1, v_2, \ldots, v_6\}\), \(H'\) is blue, and \(F_1= 3K_2\) is red. We may assume that \((v_1, v_2, v_3, v_1)\) and \((v_3, v_4, v_5, v_3)\) are two copies of \(K_3\) in \(H'\) and \(E(F_1) = \{v_1v_4, v_2v_5, v_3v_6\}\).
First, suppose that there is a blue edge between \(\{v_1, v_2, \ldots, v_6\}\) and \(\{v_7, v_8\}\), say \(v_7v_1\) is blue. Then there is a blue \(F_4=3K_2\) with edge set \(\{v_7v_1, v_2v_3, v_4v_5\}\) that is edge-disjoint from \(F_1, F_2, F_3\) and so \(F_1, F_2, F_3, F_4\) are four pairwise edge-disjoint monochromatic copies of \(3K_2\) in \(G\). Next, suppose that all edges between \(\{v_1, v_2, \ldots, v_6\}\) and \(\{v_7, v_8\}\) are red. Then there are two edge-disjoint red copies \(F'\) and \(F''\) of \(3K_2\) where \(E(F')=\{v_7v_1, v_8v_2, v_3v_6\}\) and \(E(F'')=\{v_7v_4, v_8v_6, v_2v_5\}\). Since \(F'\) and \(F''\) are edge-disjoint from \(F_2\) and \(F_3\), it follows that \(F', F'', F_2, F_3\) are four pairwise edge-disjoint monochromatic copies of \(3K_2\) in \(G\). ◻
While the exact value of \(ER_t(3K_2)\) is not known when \(t \ge 5\), we do have bounds for \(ER_t(3K_2)\) for integers \(t\ge 5\). First, we present some preliminary information. A vertex and an incident edge are said to cover each other. A vertex cover in a graph \(G\) is a set of vertices that covers all edges of \(G\). The minimum number of vertices in a vertex cover of \(G\) is the vertex covering number \(\beta(G)\) of \(G\). A vertex cover of cardinality \(\beta(G)\) is a minimum vertex cover in \(G\). We mentioned that \(ER_t(F) \le ER_{t+1}(F)\) for every graph \(F\) and every positive integer \(t\) in Observation 1.4. In fact, \(ER_{t+1}(F)\) can never exceed \(ER_t(F)\) by more than \(\beta(F)\).
Proposition 2.7. [7] For every nonempty graph \(F\) and each positive integer \(t\), \[ER_{t+1}(F) \le ER_{t}(F)+\beta(F).\]
Since \(\beta(3K_2) = 3\), it follows by Proposition 2.7 that \(ER_{t+1}(3K_2) \le ER_{t}(3K_2)+3\) for each positive integer \(t\). In fact, \(ER_{t+1}(3K_2) \le ER_{t}(3K_2)+2\) for each positive integer \(t\). In order to establish this fact, we first present two lemmas.
Lemma 2.8. Let \(k\) and \(t\) be integers with \(k \ge t+4 \ge 8\). Then \(\frac{1}{2} \left[{k \choose 2} – 3t\right] \ge k.\)
Proof. Since \(t+4 \ge 8\), it follows that \(t \ge 4\) and so \((t-4)(t+1) \ge 0\). Therefore, \[(t-4)(t+1) = t^2 -3t -4 = t^2 +3t-4-6t = (t+4)(t-1)-6t \ge 0.\]
Since \(k \ge t+4\), it follows that \(k-5 \ge t-1\) and so \(k(k-5) – 6t \ge (t+4)(t-1)-6t\ge 0.\) Thus, \(k^2-5k-6t \ge 0\) and so \(k^2-k-6t \ge 4k\). Therefore, \(\frac{k^2-k}{2} – 3t \ge 2k\) and so \(\frac{1}{2} \left[{k \choose 2} – 3t\right] \ge k.\) ◻
Lemma 2.9. If \(G\) is a graph of size \(m\), then \(\alpha'(G) \ge \frac{m}{\Delta(G)}\) where \(\Delta(G)\) is the maximum degree of \(G\).
Proof. Let \(\{E_1, E_2, \ldots, E_k\}\) be a partition of \(E(G)\) into independent sets. Since \(|E_i| \le \alpha'(G)\) for \(1 \le i \le k\), it follows that \(m = \sum_{i=1}^k |E_i| \le k\alpha'(G)\) and so \(k \ge \frac{m}{\alpha'(G)}\). Hence, every partition of \(E(G)\) into independent sets must contain at least \(\frac{m}{\alpha'(G)}\) sets. If \(v \in V(G)\) with \(\deg v = \Delta(G)\), then each of the \(\Delta(G)\) edges incident with \(v\) must belong to distinct independent sets of edges. Thus, \(\Delta(G) \ge \frac{m}{\alpha'(G)}\) and so \(\alpha'(G) \ge \frac{m}{\Delta(G)}\). ◻
We are now prepared to present the following.
Theorem 2.10. Let \(t\) be a positive integer. If \(ER_t(3K_2) \ge t+4\), then \(ER_{t+1}(3K_2) \le ER_t(3K_2)+2\).
Proof. Since the statement is true for \(t =1, 2, 3\), we may assume that \(t \ge 4\). Let \(ER_t(3K_2)=k \ge t+4 \ge 8\). Let \(c\) be a red-blue coloring of \(G = K_{k+2}\) with \(V(G)=\{v_1, v_2, \ldots, v_{k+2}\}\). We show that there are \(t+1\) pairwise edge-disjoint monochromatic copies of \(3K_2\) in \(G\). Let \(F = G[\{v_1, v_2, \ldots, v_k\}] = K_k\). Since \(ER_t(3K_2)=k\), there are \(t\) pairwise edge-disjoint monochromatic copies \(Q_1, Q_2, \ldots, Q_t\) of \(3K_2\) in \(F\). Let \(H\) be the spanning subgraph of \(F\) whose edge set consists of all edges of \(G\) that do not belong to any of \(Q_1, Q_2, \ldots, Q_t\). That is, \[H=F -[E(Q_1)\cup E(Q_2) \cup \cdots \cup E(Q_t)].\]
Thus, \(H\) is a graph of order \(k\) and size \({k\choose 2}-3t\). Let \(H_r\) be the red subgraph of \(H\) and \(H_b\) the blue subgraph of \(H\). We may assume that \(|E(H_r)|=m_r \ge m_b=|E(H_b)|\). If \(\alpha'(H_r) \ge 3\) or \(\alpha'(H_b) \ge 3\), then there is a monochromatic \(3K_2\) that is edge-disjoint from \(Q_1, Q_2, \ldots, Q_t\). Thus, we may assume that \(\alpha'(H_r) \le 2\) and \(\alpha'(H_b) \le 2\).
Observe that if \(\alpha'(H_r) \le 2\), then \(H_b\) is not empty, for otherwise, since \(k \ge t+4\ge 8\), it follows by Lemma 2.8 that \(m_r = {k\choose 2}-3t \ge 2k\). Furthermore \(\Delta(H_r) \le k-1\). Thus, \(\alpha'(H_r) \ge \frac{m_r}{\Delta(H_r)} \ge \frac{2k}{k-1}\) by Lemma 2.9 and so \(\alpha'(H_r) \ge 3\), a contradiction.
Since \(m_r \ge m_b\), we have \(m_r \ge \frac{1}{2} \left[{k\choose 2}-3t\right]\). Because \(k \ge t+4\ge 8\), it follows by Lemma 2.8 that \(\frac{1}{2} \left[{k\choose 2}-3t\right]\ge k\). Thus, \(H_r\) has order \(k\ge 8\) and size at least \(k\). Hence, \(H_r\) is neither a star nor \(K_3\) and so \(\alpha'(H_r) \ge 2\). Hence, \(\alpha'(H_r)=2\), say \(v_1v_2\) and \(v_3v_4\) are two edges in \(H_r\). First, we make some observations.
(1) If there is a red edge in \(H_r\) that is incident with two vertices in \(\{v_5, v_6, \ldots, v_{k}\}\), say \(v_5v_6 \in E(H_r)\), then \(v_1v_2\), \(v_3v_4\), \(v_5v_6\) form a red \(3K_2\) that is edge-disjoint from \(Q_1, Q_2, \ldots, Q_t\). Thus, no edge of \(H_r\) belongs to \(G[\{v_5, v_6, \ldots, v_{k}\}]\).
(2) If \(v_{k+1}\) or \(v_{k+2}\) is joined to a vertex \(v_i\) (\(5 \le i \le k\)) by a red edge, say \(v_{k+1}v_5\) is red, then \(v_1v_2\), \(v_3v_4\), \(v_{k+1}v_5\) form a red \(3K_2\) that is edge-disjoint from \(Q_1, Q_2, \ldots, Q_t\). Thus, \(v_{k+1}v_i\) and \(v_{k+2}v_i\) are blue for \(5 \le i \le k\). Furthermore, \(v_{k+1}v_{k+2}\) is blue, for otherwise, \(v_1v_2\), \(v_3v_4\), \(v_{k+1}v_{k+2}\) form a red \(3K_2\) that is edge-disjoint from \(Q_1, Q_2, \ldots, Q_t\).
Since \(\alpha'(H_b) \le 2\), we consider these two cases.
Case 1. \(\alpha'(H_b) = 2\). Let \(e, f \in E(H_b)\) be two nonadjacent edges in \(H_b\). Since \(v_{k+1}v_{k+2}\) is blue by (2), it follows that \(e\), \(f\), \(v_{k+1}v_{k+2}\) form a blue \(3K_2\) that is edge-disjoint from \(Q_1, Q_2, \ldots, Q_t\).
Case 2. \(\alpha'(H_b) = 1\). Let \(v_pv_q\in E(H_b)\). Since \(k\ge 8\), there are \(i, j \in \{5, 6, \ldots, k\}-\{p, q\}\) and \(i \ne j\). Then \(v_pv_q\), \(v_{k+1}v_{i}\), \(v_{k+2}v_j\) form a blue \(3K_2\) that is edge-disjoint from \(Q_1, Q_2, \ldots, Q_t\) ◻
.
With the aid of Theorem 2.10, we now present bounds for \(ER_t(3K_2)\) for each integer \(t \ge 4\).
Theorem 2.11. For each integer \(t \ge 4\), \[\left\lceil \frac{5 + \sqrt{1+24t}}{2}\right\rceil \le ER_t(3K_2) \le 2t.\]
Proof. To verify the upper bound, we proceed by induction on \(t\). Since \(ER_4(3K_2) = 8\) by Theorem 2.6, the result is true for \(t = 4\). Assume that \(ER_t(3K_2) \le 2t\) for some integer \(t \ge 4\). By Theorem 2.10 and the induction hypothesis, \(ER_{t+1}(3K_2) \le ER_{t}(3K_2)+2\le 2t+ 2=2(t+1)\).
To verify a lower bound, let \(ER_t(3K_2) = k\). Then every red-blue coloring of \(K_k\) produces at least \(t\) pairwise edge-disjoint copies of \(3K_2\). Consider the red-blue coloring of \(G=K_k\) with red subgraph \(G_r=K_2\vee \overline{K}_{k-2}\) and blue subgraph \(G_b=K_{k-2}+\overline{K}_2\). Since \(\alpha'(G_r)= 2\), there is no red \(3K_2\). Hence, \(G_b\) contains at least \(t\) pairwise edge-disjoint monochromatic copies of \(3K_2\). This implies that \(|E(G_b)| = {k-2\choose 2} \ge 3t\) or \(k^2-5k+6-6t \ge 0\). Thus, \(ER_t(3K_2)= k \ge \left\lceil \frac{5 + \sqrt{1+24t}}{2}\right\rceil.\) ◻
Note that the lower bound in Theorem 2.11 holds for every positive integer \(t\). We saw that \(ER_t(3K_2) = t+4\) when \(t = 4\) by Theorem 2.6 and for each integer \(t \ge 2\), if \(ER_t(3K_2) \ge t+4\), then \(ER_{t+1}(3K_2) \le ER_t(3K_2)+2\) by Theorem 2.10. Should it over occurs that \(ER_t(3K_2)\ge t+4\) for some \(t \ge 10\), then \(ER_{t+1}(3K_2) \le ER_t(3K_2)+1\). To show this, we first state a lemma whose proof is similar to that of Lemma 2.8.
Lemma 2.12. Let \(k\) and \(t\) be integers with \(k \ge t+4 \ge 14\). Then \(\frac{1}{2} \left[{k \choose 2} – 3t\right] \ge 2k.\)
Theorem 2.13. Let \(t \ge 10\) be an integer. If \(ER_t(3K_2) \ge t+4\), then \(ER_{t+1}(3K_2) \le ER_t(3K_2)+1\).
Proof. Let \(ER_t(3K_2)=k \ge t+4 \ge 14\). Let \(c\) be a red-blue coloring of \(G = K_{k+1}\) with \(V(G)=\{v_1, v_2, \ldots, v_{k+1}\}\). We show that there are \(t+1\) pairwise edge-disjoint monochromatic copies of \(3K_2\) in \(G\). Let \(F = G[\{v_1, v_2, \ldots, v_k\}] = K_k\). Since \(ER_t(3K_2)=k\), there are \(t\) pairwise edge-disjoint monochromatic copies \(Q_1, Q_2, \ldots, Q_t\) of \(3K_2\) in \(F\). Let \[H=F -[E(Q_1)\cup E(Q_2) \cup \cdots \cup E(Q_t)].\]
Thus, \(H\) is a graph of order \(k\) and size \({k\choose 2}-3t\). Let \(H_r\) be the red subgraph of \(H\) and \(H_b\) the blue subgraph of \(H\). We may assume that \(|E(H_r)|=m_r \ge m_b=|E(H_b)|\). Hence, \(m_r \ge \frac{1}{2} \left[{k \choose 2} – 3t\right] \ge 2k\) by Lemma 2.12. Furthermore \(\Delta(H_r) \le k-1\). Thus, \(\alpha'(H_r) \ge \frac{m_r}{\Delta(H_r)} \ge \frac{2k}{k-1}\) by Lemma 2.9 and so \(\alpha'(H_r) \ge 3\). Therefore, \(H_r\) contains a copy of \(3K_2\) that is edge-disjoint from \(Q_1, Q_2, \ldots, Q_t\). ◻
We now turn our attention to the vertex-disjoint and edge-disjoint Ramsey numbers of \(P_3+P_2\). With the aid of Proposition 2.1, we are able to determine \(VR_t(P_3+P_2)\) for every positive integer \(t\).
Theorem 3.1. For each positive integer \(t\), \(VR_{t}(P_3+P_2) = 5t+1\).
Proof. Since \(VR_1(P_3+P_2) =R(P_3+P_2)= 6\) and the order of \(P_3+P_2\) is 5, it follows by Proposition 2.1 that \(VR_{t}(P_3+P_2) \le 6+5(t-1)= 5t+1\).
Next, consider the red-blue coloring of \(G = K_{5t}\) with red subgraph \(G_r=K_{1, 5t-1}\) and blue subgraph \(G_b = K_{5t-1}\). Then there is no red \(P_3+P_2\) in \(G_r\). The blue subgraph \(G_b\) has order \(5t-1\) and so there are no \(t\) pairwise vertex-disjoint blue copies of \(P_3+P_2\). Since this red-blue coloring has no \(t\) pairwise vertex-disjoint monochromatic copies of \(P_3+P_2\), it follows that \(VR_t(P_3+P_2) \ge 5t+1\) and so \(VR_{t}(P_3+P_2) = 5t+1\). ◻
We now consider edge-disjoint Ramsey numbers of \(P_3+P_2\). We begin with \(ER_t(P_3+P_2)\) for \(t =2, 3, 4\). First, we present a useful lemma.
Lemma 3.2. Let \(G\) be a graph of order \(n \ge 6\) and size \(m \ge 6\) with \(\Delta(G) \ge 2\). If \(G \notin \{K_4+\overline{K}_{n-4}, K_{1, m}+ \overline{K}_{n-m-1}\}\), then \(P_3+P_2 \subseteq G\).
Proof. Let \(\Delta(G) =\Delta\) and let \(v \in V(G)\) such that \(\deg v = \Delta\) where \(N(v)=\{v_1, v_2, \ldots, v_{\Delta}\}\).
\(\star\) First, suppose that \(\Delta(G) = 2\). Then each component of \(G\) is a cycle or a path. Since \(m \ge 6\), it follows that \(P_3+P_2 \subseteq G\).
\(\star\) Next, suppose that \(\Delta(G) = 3\). Since \(G \ne K_4+\overline{K}_{n-4}\) and \(m \ge 6\), there is an edge not in the subgraph \(G[N[v]]\) induced by the closed neighborhood \(N[v]\) of \(v\) in \(G\). Hence, \(P_3+P_2 \subseteq G\).
\(\star\) Finally, suppose that \(\Delta(G) \ge 4\). Since \(G \ne K_{1, \Delta}+ \overline{K}_{n-\Delta-1}\), there is an edge that is not incident with \(v\) and so \(P_3+P_2 \subseteq G\). ◻
Theorem 3.3. \(R(P_3+P_2)=ER_2(P_3+P_2)=6\).
Proof. First, we show that \(R(P_3+P_2) = 6\). The red-blue coloring of \(K_5\) with red subgraph \(K_{1, 4}\) and blue subgraph \(K_4\) contains no monochromatic \(P_3+P_2\). Thus, \(R(P_3+P_2) \ge 6\). Let there be given an arbitrary red-blue coloring of \(G=K_6\). Let \(G_r\) be the red subgraph of \(G\) and \(G_b\) the blue subgraph of \(G\). Suppose that the size of \(G_r\) is \(m_r\) and the size of \(G_b\) is \(m_b\). Thus, \(m_r+m_6= 15\). We may assume that \(m_r \ge m_b\) and so \(m_r \ge 8\). Since \(G_r\) has order 6 and size \(m_r \ge 8\), it follows that \(G_r \notin \{K_{1, m_r}, K_4+\overline{K}_2\}\) and so \(P_3+P_2 \subseteq G_r\) by Lemma 3.2. Therefore, \(R(P_3+P_2) \le 6\) and so \(R(P_3+P_2) = 6\).
Next, we show that \(ER_2(P_3+P_2) = 6\). First, \(ER_2(P_3+P_2) \ge R(P_3+P_2) = 6\). Let there be given an arbitrary red-blue coloring of \(G=K_6\). Since \(R(P_3+P_2) = 6\), there is a monochromatic subgraph \(F= P_3 + P_2\) of \(G\). Let \(H = G-E(F)\). Thus, \(H\) has order 6 and size \({6 \choose 2}-3=12\). Let \(H_r\) be the red subgraph of size \(m_r\) and \(H_b\) the blue subgraph of size \(m_b\). Thus, \(m_r+m_6= 12\). We may assume that \(m_r \ge m_b\) and so \(m_r \ge 6\).
If \(m_r \ge 7\), then \(H_r \notin \{K_{1, 6}, K_4+\overline{K}_{2}\}\) and so \(P_3+P_2\subseteq H_r\) by Lemma 3.2. Hence, we may assume that \(m_r = m_b= 6\).
Thus, \(H_r\) and \(H_b\) both have order 6 and size 6. So, neither \(H_r\) nor \(H_b\) is \(K_{1, 6}\). Since \(H_r\) and \(H_b\) are not both \(K_4+\overline{K}_{2}\), we may assume that \(H_r \ne K_4+\overline{K}_{2}\). Therefore, \(H_r \notin \{K_{1, 6}, K_4+\overline{K}_{2}\}\) and so \(P_3+P_2\subseteq H_r\) by Lemma 3.2. Therefore, \(G\) has two edge-disjoint copies of \(P_3+P_2\). Hence, \(ER_2(P_3+P_2) \le 6\) and so \(ER_2(P_3+P_2) = 6\). ◻
Theorem 3.4. \(ER_3(P_3+P_2)=ER_4(P_3+P_2)=7\).
Proof. Let there be given a red-blue coloring of \(H= K_6\) with red subgraph \(H_r= K_2 \vee \overline{K}_4\) and blue subgraph \(H_b=K_4+\overline{K}_2\). The blue subgraph \(H_b\) fails to contain a copy of \(P_3+P_2\). Since there are not three pairwise edge-disjoint red copies of \(P_3+P_2\) in \(H\), it follows that \(ER_4(P_3+P_2)\ge ER_3(P_3+P_2)\ge 7\). First, we show that \(ER_3(P_3+P_2) = 7\). Let there be given an arbitrary red-blue coloring of \(G=K_7\). Since \(ER_2(P_3+P_2) = 6\), there are edge-disjoint monochromatic copies \(F_1\) and \(F_2\) of \(P_3+P_2\) in \(G\). Let \(H= G-(E(F_1)\cup E(F_2))\). Then \(H\) has order 7 and size \({7\choose 2}-2\cdot 3 = 15\). Let \(H_r\) be the red subgraph of \(H\) and \(H_b\) the blue subgraph of \(H\). Suppose that the size of \(H_r\) is \(m_r\) and the size of \(H_b\) is \(m_b\). Thus, \(m_r+m_6= 15\). We may assume that \(m_r \ge m_b\) and so \(m_r \ge 8\). Since \(H_r\) has order 7 and size \(m_r \ge 8\), it follows that \(H_r \notin \{K_{1, m_r}, K_4+\overline{K}_{3}\}\) and so \(P_3+P_2 \subseteq H_r\) by Lemma 3.2. Therefore, \(ER_3(P_3+P_2) \le 7\) and so \(ER_3(P_3+P_2) = 7\).
Next, we show that \(ER_4(P_3+P_2) = 7\). Let there be given an arbitrary red-blue coloring of \(G=K_7\). Since \(ER_3(P_3+P_2) = 7\), there are three pairwise edge-disjoint monochromatic copies \(F_1, F_2, F_3\) of \(P_3+P_2\) in \(G\). Let \(H= G-(E(F_1)\cup E(F_2))\cup E(F_3)\). Then \(H\) has order 7 and size \({7\choose 2}-3\cdot 3 = 12\). Let \(H_r\) of size \(m_r\) be the red subgraph of \(H\) and \(H_b\) of size \(m_b\) the blue subgraph of \(H\). Thus, \(m_r+m_b= 12\). We may assume that \(m_r \ge m_b\) and so \(m_r \ge 6\). Thus, \(H_r\) has order 7 and size \(m_r \ge 6\). If \(m_r \ge 7\), then \(H_r \notin \{K_{1, 7}, K_4+\overline{K}_{3}\}\) and so \(P_3+P_2\subseteq H_r\) by Lemma 3.2. Hence, we may assume that \(m_r =m_b= 6\). Thus, both \(H_r\) and \(H_b\) both have order 7 and size 6. We verify the following claim.
Claim: At least one of \(H_r\) and \(H_b\) is neither \(K_{1, 6}\) nor \(K_4+\overline{K}_{3}\).
To verify the claim, suppose that \(H_b \in \{K_{1, 6}, K_4+\overline{K}_{3}\}\). We show that \(H_r \notin \{K_{1, 6}, K_4+\overline{K}_{3}\}\). Let \(V(H)=\{v_1, v_2, \ldots, v_7\}\). First, suppose that \(H_b = K_{1, 6}\). Then \(H_r \ne K_{1, 6}\). Assume that \(H_r = K_4+\overline{K}_{3}\). Let \(v_7\) be the center of \(H_b\) and so \(v_7\) is adjacent to \(v_1, v_2, \ldots, v_6\) in \(H_b\). For the subgraph \(K_4\) in \(H_r\), we may assume that \(V(K_4) = \{v_3, v_4, v_5, v_6\}\). However then, \(H'= G-(E(H_r)\cup E(H_b)) = G -E(H)= K_2 \vee \overline{K}_4\). Since \(G-E(H)\) is decomposed into \(F_1, F_2, F_3\) and \(K_2 \vee \overline{K}_4\) cannot be decomposed into three copies of \(P_3+P_2\), this is a contradiction. Thus, \(H_r \ne K_4+\overline{K}_{3}\) and so \(H_r \notin \{K_{1, 6}, K_4+\overline{K}_{3}\}\). By symmetry, we may assume that \(\{H_r, H_b\} \ne \{K_{1, 6}, K_4+\overline{K}_{3}\}\). Next, suppose \(H_b = K_4+\overline{K}_{3}\) where say \(V(K_4)=\{v_4, v_5, v_6, v_7\}\). Then \(H_r \ne K_{1, 6}\). Since \(v_1, v_2, v_3\) are the only possible vertices in \(H-E(H_b)\) having degree 3 or more and \(H_r \subseteq H-E(H_b)\), it follows that \(H_r \ne K_4+\overline{K}_{3}\). Therefore, \(H_r \notin \{K_{1, 6}, K_4+\overline{K}_{3}\}\). Thus, the claim holds. So, we may assume that \(H_r \notin \{K_{1, 6}, K_4+\overline{K}_{3}\}\). It then follows by Lemma 3.2 that \(P_3+P_2 \subseteq H_r\). Hence, there is a monochromatic copy of \(P_3+P_2\) edge-disjoint from \(F_1, F_2, F_3\). Therefore, \(ER_4(P_3+P_2) \le 7\) and so \(ER_4(P_3+P_2) = 7\). ◻
While the exact value of \(ER_t(P_3+P_2)\) is not known when \(t \ge 5\), we do have bounds for \(ER_t(P_3+P_2)\) for every positive integer \(t\). Since \(\beta(P_3+P_2) = 2\), the following is a consequence of Proposition 2.7.
Corollary 3.5. For each positive integer \(t\), \(ER_{t+1}(P_3+P_2) \le ER_{t}(P_3+P_2)+2\).
With the aid of Theorem 3.4 and Corollary 3.5, we now present bounds for \(ER_t(P_3+P_2)\) for each integer \(t \ge 4\).
Theorem 3.6. For each integer \(t \ge 4\), \(\left\lceil \frac{3 + \sqrt{1+24t}}{2}\right\rceil \le ER_t(P_3+P_2) \le 2t-1.\)
Proof. To verify the upper bound, we proceed by induction on \(t\). Since \(ER_4(P_3+P_2) = 7\) by Theorem 3.4, the result is true for \(t = 4\). Assume that \(ER_t(P_3+P_2) \le 2t-1\) for some integer \(t \ge 4\). By Proposition 3.5 and the induction hypothesis, \(ER_{t+1}(P_3+P_2) \le ER_{t}(P_3+P_2)+2\le (2t-1)+ 2=2(t+1)-1\).
To verify the lower bound, let \(ER_t(P_3+P_2) = k\). Then every red-blue coloring of \(K_k\) produces at least \(t\) pairwise edge-disjoint monochromatic copies of \(P_3+P_2\). Consider the red-blue coloring of \(G=K_k\) with red subgraph \(G_r=K_{1, k-1}\) and blue subgraph \(G_b=K_{k-1}\). Since there is no red \(P_3+P_2\), it follows that \(G_b\) contains at least \(t\) pairwise edge-disjoint monochromatic copies of \(P_3+P_2\). This implies that \(|E(G_b)| = {k-1\choose 2} \ge 3t\) or \(k^2-3k+(2-6t) \ge 0\). Consequently, \(ER_t(P_3+P_2)= k \ge \left\lceil \frac{3 + \sqrt{1+24t}}{2}\right\rceil\). ◻
Here too, the lower bound for \(ER_t(P_3+P_2)\) in Theorem 3.6 holds for each positive integer \(t\). We saw that \(R(P_3+P_2)=ER_2(P_3+P_2)= 6\) and \(ER_3(P_3+P_2)=ER_4(P_3+P_2)= 7\). Therefore, \(ER_t(P_3+P_2) = t+3\) for \(t = 4\). Should it ever occur that \(ER_t(P_3+P_2) \ge t+3\) for some integer \(t \ge 7\), then \(ER_{t+1}(P_3+P_2) \le ER_t(P_3+P_2)+1\). To establish this, we first state a lemma whose proof is similar to that of Lemma 2.8.
Lemma 3.7. Let \(k\) and \(t\) be integers with \(k \ge t+3 \ge 10\). Then \(\frac{1}{2} \left[{k \choose 2} – 3t\right] \ge k+1.\)
Theorem 3.8. Let \(t \ge 7\) be an integer. If \(ER_t(P_3+P_2) \ge t+3\), then \(ER_{t+1}(P_3+P_2) \le ER_t(P_3+P_2)+1\).
Proof. Let \(ER_t(P_3+P_2)=k \ge t+3 \ge 10\). Let \(c\) be a red-blue coloring of \(G = K_{k+1}\) with \(V(G)=\{v_1, v_2, \ldots, v_{k+1}\}\). We show that there are \(t+1\) pairwise edge-disjoint monochromatic copies of \(P_3+P_2\) in \(G\). Let \(F = G[\{v_1, v_2, \ldots, v_k\}] = K_k\). Since \(ER_t(P_3+P_2)=k\), there are \(t\) pairwise edge-disjoint monochromatic copies \(Q_1, Q_2, \ldots, Q_t\) of \(P_3+P_2\) in \(F\). Let \[H=F -[E(Q_1)\cup E(Q_2) \cup \cdots \cup E(Q_t)].\]
Thus, \(H\) is a graph of order \(k\) and size \({k\choose 2}-3t\). Let \(H_r\) be the red subgraph of \(H\) and \(H_b\) the blue subgraph of \(H\). We may assume that \(|E(H_r)|=m_r \ge m_b=|E(H_b)|\). Hence, \(m_r \ge \frac{1}{2} \left[{k \choose 2} – 3t\right] \ge k+1\) by Lemma 3.7. Since \(H_r\) is a graph of order \(k \ge 10\) and size at least \(k+1\), it follows that \(H_r\) is neither a star \(K_{1, k-1}\) nor the unicyclic graph \((K_2+ \overline{K}_{k-3})\vee K_1\). Therefore, \(H_r\) contains a copy of \(P_3+P_2\) that is edge-disjoint from \(Q_1, Q_2, \ldots, Q_t\). ◻
We are grateful to Professor Gary Chartrand for suggesting the concepts and problems to us and kindly providing useful information on this topic. Furthermore, we thank the anonymous referee whose valuable suggestions resulted in an improved paper.