1 Introduction

All graphs in this paper are undirected, finite and simple. The union of two graphs G and H, denoted by \(G\cup H,\) is a graph with vertex set \(V(G) \cup V(H)\) and edge set \(E(G) \cup E(H)\). The join of two graphs G and H, denoted by \(G+H,\) is a graph with vertex set \(V(G) \cup V(H)\) and edge set \(E(G) \cup E(H) \cup \lbrace uv \vert u\in V(G), v\in V(H) \rbrace \). The union of k disjoint copies of the same graph G is denoted by kG. \({\overline{G}}\) stands for the complement of the graph G. We denote by G[U] the subgraph of G induced by the vertex set U. By \(P_n\) and \(C_n\) we denote the path and cycle on n vertices, respectively. For a 3-edge coloring (say blue, red and green) of a graph G, we denote by \(G^{b}\) (\(G^{r}\) and \(G^{g}\)) the subgraph induced by the edges of color blue (red and green, respectively).

For given graphs \(G_{1}, G_{2},\ldots , G_{k}, k \ge 2\), the multicolor Ramsey number\(R(G_{1}, G_{2},\ldots , G_{k})\) is the smallest integer n such that if we arbitrarily color the edges of the complete graph of order n with k colors, then it contains a monochromatic copy of \(G_{i}\) in color i, for some \(1 \le i \le k\). The existence of such a positive integer is guaranteed by Ramsey’s classical result [17]. Ramsey numbers are still in the main stream of investigations and there are no many results in the field of multicolor and even three-color Ramsey numbers. There are a lot of open cases (see [18]).

The bipartite Ramsey number \(b(G_1, \ldots , G_k)\) is the smallest positive integer b such that any coloring of the edges of \(K_{b,b}\) with k colors contains a monochromatic copy of bipartite \(G_i\) in the i-th color, for i, \(1 \le i \le k\).

In 2005, the second author began to determine the exact values for three color Ramsey numbers for two paths and one cycle. He proved that for \(n \ge 6\), \(R(P_3,P_3,C_n)=n\) and \(R(P_3,P_4,C_n)=n+1\) [4]. In 2006 Dzido et al. [6] proved that \(R(P_4,P_4,C_n)=n+2\) and \(R(P_3,P_5,C_n)=n+1\). In 2009 Dzido and Fidytek [5] (and independently Bielak in [2]) obtained the exact value of \(R(P_{i},P_{k},C_{m})\) for several values of i, k and m.

Theorem 1

[2, 5] Let i, k, m be integers such that \(m \ge 3\) is odd, \(k \ge m,\) and \(k > \frac{3i^2-14i+25}{4}\) when i is odd,  and \(k > \frac{3i^2-10i+20}{8}\) when i is even. Then

$$\begin{aligned} R(P_i,P_k,C_m) = 2k + 2\Big \lfloor \frac{i}{2} \Big \rfloor - 3. \end{aligned}$$

In Sect. 3.1 we extend this result to other conditions on the length of paths and a cycle. By a short proof we show that for integers \(n_0, n_1, n_2\) such that \(n_0\) is sufficiently large, if \( n_{1}=2s\) and \(n_{2}=2m\) such that \(m-1<2s\), or \(n_{1}=n_{2}=2s\) or \(n_{1}=2s+1\) and \(n_{2}=2m\) such that \(s<m-1<2s+1\) then

$$\begin{aligned} R(C_{n_0}, P_{n_{1}},P_{n_{2}}) = n_0 + \Big \lfloor \frac{n_1}{2} \Big \rfloor + \Big \lfloor \frac{n_2}{2} \Big \rfloor -2. \end{aligned}$$

It should be noted that this result can be also obtained as a consequence of Theorem 2.2 in [14].

For the Ramsey number of paths a well-known theorem of Gerencsér and Gyárfás [10] states that \(R(P_{n},P_{m})=m+\lfloor n/2 \rfloor -1\) where \(m \ge n \ge 2\). In 1975 [7] Faudree and Schelp determined \(R(P_{n_1},P_{n_2},P_{n_3})\) for the case \(n_{1}\ge 6(n_{2}+n_{3})^{2}\) and they conjectured that

$$\begin{aligned} R(P_{n},P_{n},P_{n}) = \left\{ \begin{array}{ll} 2n-2 &{} \quad \text {if } n \text { is even},\\ 2n-1 &{} \quad \text {if } n \text { is odd}. \end{array} \right. \end{aligned}$$

In 2007 this conjecture was established by Gyárfás et al. [11] for sufficiently large n. We can apply our result for \(R(C_{n_0}, P_{n_{1}},P_{n_{2}})\) to \(P_{n_0}\) instead of \(C_{n_0}\) to obtain the same result as in [7]. The formula is the same but the original result contains the lower bound for \(n_0\) and no conditions for \(n_1\) and \(n_2\) (except \(n_1, n_2 \ge 2\)).

The Ramsey number of a star versus a path was completely determined by Parsons [15]. In Sects. 3.3 and 3.6 we investigate multicolor Ramsey number of a cycle \(C_n\) or path \(P_n\) versus stars and stripes for large value of n.

In [13] Maherani et al. proved that \(R(P_{3}, kK_{2}, tK_{2})=2k+t-1\) for \(k\ge t \ge 3\). In this paper we show that \(R(P_n,kK_{2},tK_{2})=n+k+t-2\) for large n. In addition we prove that for even k, \(R((k-1)K_{2},P_{k},P_{k})=3k-4\). For \(s< m-1<2s+1\) and \(t\ge m+s-1\), we obtain that \(R(tK_{2},P_{2s+1},P_{2m})=s+m+2t-2.\)

We also provide some new exact values or generalize known results for other multicolor Ramsey numbers of paths, cycles, stripes and stars versus other graphs.

2 Main Results

Theorem 2

For every graph H and bipartite graphs \(G_1, \ldots , G_k,\) we have

$$\begin{aligned} R(H,G_1,\ldots ,G_k)\le R(H, K_{b,b}), \end{aligned}$$

where \(b=b(G_1, \ldots , G_k)\).

Proof

Assume \(R(H, K_{b,b})=n\), we will show that for any coloring of the edges of the complete graph \(K_{n}\) by \(k+1\) colors there exists a color i for which the corresponding color class contains \(G_{i}\) as a subgraph.

Suppose that \(G=K_{n}\) is \((k+1)\)-edge colored such that G does not contain H of color 1. We show that there is a copy of \(G_{i}\) of color i in G for some \(2\le i\le k+1\). Now we merge k colors classes \(2, \ldots , k+1\). Suppose that new class is black. Since \(R(H, K_{b,b})=n\), we have a black copy of \(K_{b,b}\). Using to its original k-coloring, we see that there exists a complete bipartite subgraph \(L=K_{b,b}\) whose edges are colored with \(2,\ldots ,k+1\) (observe that there is no edges of color 1 in L). Now \(b=b(G_1, \ldots , G_k)\) guarantees that L contains a copy of \(G_{i}\) of color i for some \(2\le i\le k+1\).

Häggkvist [12] obtained the upper bound \(R(P_{m},K_{n,k})\le k+n+m-2.\) In addition, Faudree et al. [9] obtained the exact value \(R(tK_{2},K_{n,n})=max \lbrace n+2t-1,2n+t-1 \rbrace .\) Using these results with Theorem 2 we immediately obtain the following.

Corollary 1

For bipartite graphs \(G_1, \ldots , G_k,\) we have

  1. 1.
    $$\begin{aligned} R(P_{m}, G_1,\ldots ,G_k)\le 2b+m-2, \end{aligned}$$
  2. 2.
    $$\begin{aligned} R(tK_{2}, G_1,\ldots , G_k) \le {\left\{ \begin{array}{ll} 2b+t-1 &{} \text {if } t \le b, \\ b+2t-1 &{} \text {if } t \ge b, \end{array}\right. } \end{aligned}$$

    where \(b=b(G_1, \ldots , G_k)\).

For bipartite graphs \(G_1, G_2, \ldots , G_k\) we easily have \(R(G_1, G_2, \ldots , G_k) \le 2b(G_1, G_2, \ldots , G_k)\). The answer to the question when the equality holds is an open problem. For example, we know that \(b(C_{2m}, C_4) = m + 1\) for \( m \ge 4 \), while \(R(C_{2m}, C_4) = 2m + 1\) for \( m \ge 3 \) (see [18, 19], respectively).

Corollary 2

If \(R(G_1, G_2, \ldots , G_k) = 2b(G_1, G_2, \ldots , G_k)=2t\) for bipartite graphs \(G_1, \ldots , G_k,\) then

$$\begin{aligned} R(tK_{2},G_1,\ldots ,G_k)=3t-1. \end{aligned}$$

Proof

By Corollary 1, the upper bound is clear. To see the lower bound consider the graph \(G=K_{3t-2}=K_{2t-1}+ K_{t-1}\). Since \(R(G_1, \ldots , G_k)=2t\), we take a k-coloring of \(E(K_{2t-1})\) which does not contain a copy of \(G_{i}\) in color i for any \(1 \le i\le k\). The remaining edges of G we color with color \((k+1)\) and clearly such \(G^{k+1}\) contains no copy of \(tK_{2}\). This proves the corollary.

3 More Corollaries

This section contains a number of corollaries following from the main Theorem 2 and some known results about Ramsey numbers and bipartite Ramsey numbers.

3.1 \(R(C_{n_{0}},P_{n_{1}},P_{n_{2}})\) for Large \(n_{0}\)

In this subsection, we determine the value of \(R(C_{n_{0}},P_{n_{1}},P_{n_{2}})\) for large \(n_{0}\) and special cases of \(n_{1}, n_{2}\). We first recall a result of Bondy and Erdős from 1973 [1] for \(n> n_{1}(r)\) (that is for sufficiently large n). More precisely, they showed the following.

Theorem 3

[1] For \(n> n_{1}(r,t),\)\(R(C_{n},K^{t+1}_{r})=t(n-1)+r\) where \(K^{t+1}_{r}\) is the complete \((t+1)\)-partite graph with parts of size r. In particular \(R(C_{n},K_{r,r})=n+r-1\).

We can apply this result and Theorem 2 to determine the value which can be also obtained as consequence of Theorem 2.2 in [14].

Theorem 4

For sufficiently large \(n_{0},\) if \(n_{1}=2s\) and \(n_{2}=2m\) such that \(m-1<2s\) or if \(n_{1}=n_{2}=2s\) or if \(n_{1}=2s+1\) and \(n_{2}=2m\) such that \(s<m-1<2s+1,\) then we have

$$\begin{aligned} R(C_{n_0}, P_{n_{1}},P_{n_{2}}) = n_0 + \Big \lfloor \frac{n_1}{2} \Big \rfloor + \Big \lfloor \frac{n_2}{2} \Big \rfloor -2. \end{aligned}$$

Proof

For the upper bound, by Theorem 2, \(R(C_{n_{0}},P_{n_{1}},P_{n_{2}})\le R(C_{n_{0}},K_{b,b})\) where \(b=b(P_{n_{1}},P_{n_{2}})\). By Theorem 3, \(R(C_{n_{0}},P_{n_{1}},P_{n_{2}})\le n_{0}+b-1\). On the other hand, \(b=\Big \lfloor \frac{n_1}{2} \Big \rfloor + \Big \lfloor \frac{n_2}{2} \Big \rfloor -1\) (see Theorem 5) and \(R(C_{n_{0}},P_{n_{1}},P_{n_{2}}) \le n_{0}+\Big \lfloor \frac{n_1}{2} \Big \rfloor + \Big \lfloor \frac{n_2}{2} \Big \rfloor -2\).

For the lower bound, consider the graph \(G=K_{R-1}\cup K_{\frac{n_2}{2}-1}\) where \(R=R(C_{n_{0}},P_{n_{1}})\). It is known that \(R=n_{0}+\Big \lfloor \frac{n_1}{2} \Big \rfloor -1\) for \(n_{0}\ge n_{1}\ge 2\). It is clear that there is a blue/red coloring of \(K_{R-1}\) such that \(G^{b}\) contains no copy of \(C_{n_{0}}\) and \(G^{r}\) contains no copy of \(P_{n_{1}}\). Color the remaining subgraph \(K_{\frac{n_2}{2}-1}\) with red. Since \(\frac{n_2}{2}-1 < n_{1}\), there is no a red copy of \(P_{n_{1}}\) in \(K_{\frac{n_2}{2}-1}\). Consider \({\overline{G}}={\overline{K}}_{R-1}+ {\overline{K}}_{\frac{n_2}{2}-1}\) and color it with green. Thus \(G^{g}\) contains no copy of \(P_{n_{2}}\). The equality follows.

In 1975 Faudree and Schelp [7] proved that if \(n_{0}\ge 6(n_{1}+n_{2})^{2}\), then \(R(P_{n_{0}},P_{n_{1}},P_{n_{2}})=n_{0}+\lfloor n_{1}/2 \rfloor +\lfloor n_{2}/2 \rfloor -2\) for \(n_{1}, n_{2}\ge 2\). Since \(R(P_{n_{0}},P_{n_{1}},P_{n_{2}}) \le R(C_{n_{0}},P_{n_{1}},P_{n_{2}})\), we can apply Theorem 4 to \(P_{n_{0}}\) instead of \(C_{n_{0}}\) to obtain the same results as in [7].

Corollary 3

For sufficiently large \(n_{0},\) if \(n_{1}=2s\) and \(n_{2}=2m\) where \(m-1<2s\) or if \(n_{1}=n_{2}=2s\) or if \(n_{1}=2s+1\) and \(n_{2}=2m\) where \(s<m-1<2s+1,\) then we have

$$\begin{aligned} R(P_{n_0}, P_{n_{1}},P_{n_{2}}) = n_0 + \Big \lfloor \frac{n_1}{2} \Big \rfloor + \Big \lfloor \frac{n_2}{2} \Big \rfloor -2. \end{aligned}$$

Proof

Since \(R(P_{n_0}, P_{n_1}) = n_{0}+\Big \lfloor \frac{n_1}{2} \Big \rfloor -1\) for \(n_{0}\ge n_{1}\ge 2\), let us consider the same graph and coloring as in the proof of Theorem 4.

3.2 \(R(tK_{2},P_{k},P_{k^{'}})\)

In 1975 Faudree and Schelp [8] determined \(b(P_{n},P_{k})\) for all n and k. In the following theorem we present only two cases which we will use in the proof of the next theorem.

Theorem 5

[8] For s, m positive integers, 

  1. 1.

    \(b(P_{2s},P_{2m})=s+m-1,\)

  2. 2.

    \(b(P_{2s+1},P_{2m})= s+m-1\) for \(s < m-1\).

Theorem 6

For positive integers k, m, s, t, 

  1. (i)

    \(R((k-1)K_{2},P_{k},P_{k})=3k-4\) if k is even, 

  2. (ii)

    \(R(tK_{2},P_{2s+1},P_{2m})=s+m+2t-2\) for \(s< m-1<2s+1\) and \(t\ge m+s-1\).

Proof

(i) Corollary 1 implies that \(R(tK_{2},P_{k},P_{k}) \le 2b+t-1\) for \(t\le b\) and \(b=b(P_{k},P_{k})\). Theorem 5 (that is \(b=b(P_{k},P_{k})=k-1\) for even k) completes the proof for the upper bound.

It is known that \(R=R((k-1)K_{2},P_{k})=2k+\lfloor k/2 \rfloor -3\) (see [9]). Consider the graph \(G=K_{R-1}\cup K_{k/2 -1}\). Clearly \(K_{R-1}\) has a blue/red coloring such that \(K_{R-1}^{b}\) contains no copy of \((k-1)K_{2}\) and \(K_{R-1}^{r}\) contains no copy of \(P_{k}\). We can take this coloring and we color the edges of \(K_{k/2 -1}\) with red. The edges of \({\overline{G}}\) we color with green. Hence \(G^{g}\) contains no copy of \(P_{k}\). This gives the desired lower bound.

(ii) As before, by Corollary 1, we have \(R(tK_{2},P_{2s+1},P_{2m}) \le b+2t-1\) for \(t\ge m+s-1\). On the other hand by Theorem 5, for \(s < m-1\), \(b(P_{2s+1},P_{2m})=s+m-1\). So for \(s < m-1\) and \(t\ge m+s-1\), \(R(tK_{2},P_{2s+1},P_{2m}) \le s+m+2t-2\).

Now, let \(G=K_{R-1}\cup K_{m-1}\) where \(R=R(tK_{2}, P_{2s+1})=2t+\lfloor (2s+1)/2 \rfloor -1\) for \(t> \lfloor (2s+1)/2 \rfloor \) (see [9]). Clearly \(K_{R-1}\) can be colored in such a way that \(K_{R-1}^{b}\) contains no copy of \(tK_{2}\) and \(K_{R-1}^{r}\) contains no copy of \(P_{2s+1}\). We color the subgraph \(K_{m-1}\) with red and the edges of \({\overline{G}}\) with green. Then \(G^{g}\) contains no copy of \(P_{2m}\) and the proof is complete.

3.3 \(R(C_n,kK_{2},tK_{2})\) and \(R(P_n,kK_{2},tK_{2})\) for Large n

Lemma 1

[3] For positive integers m and n, 

$$\begin{aligned} b(mK_{2}, nK_{2})=m+n-1. \end{aligned}$$

Theorem 7

\(R(C_n,kK_{2},tK_{2})= n+k+t-2,\) for sufficiently large n.

Proof

Theorems 2, 3 and Lemma 1 give us the desired upper bound.

In [9] it is shown that \(R(C_{n}, kK_{2})=n+k-1\) for \(k \le \lfloor \frac{n}{2} \rfloor \). Consider the graph \(G=K_{n+k-2} \cup {\overline{K}}_{t-1}\). There is a blue/red coloring of \(K_{n+k-2}\) such that \(G^{b}\) contains no copy of \(C_{n}\) and \(G^{r}\) contains no copy of \(kK_{2}\). Color \({\overline{G}}={\overline{K}}_{n+k-2}+K_{t-1}\) with color green. The theorem follows.

In [13] Maherani et al. proved that \(R(P_{3}, kK_{2}, tK_{2})=2k+t-1\) for \(k\ge t\ge 3\).

Theorem 8

\(R(P_n,kK_{2},tK_{2})= n+k+t-2,\) for sufficiently large n.

Proof

Clearly \(R(P_n,kK_{2},tK_{2})\le R(C_{n},kK_{2},tK_{2})\). Theorem 7 gives us the upper bound.

In [9] it is shown that \(R(P_{n}, kK_{2})=n+k-1\) for \(k \le \lfloor \frac{n}{2} \rfloor \). We obtain the lower bound by considering the same coloring as in the proof of Theorem 7.

3.4 \(R(tK_{2},P_{3},C_{2n})\) for \(t \le n\)

Theorem 9

[18] \(R(P_{3},C_{2n})=2n\).

Theorem 10

For positive integers \(t \le n,\)\(R(tK_{2},P_{3},C_{2n})= 2n+t-1\).

Proof

It is easy to see that \(b(P_{3},C_{2n})=n\) for \(n\ge 3\). By Corollary 1, we have \(R(tK_{2},C_{2n},P_{3})\le 2n+t-1\) where \(t \le n\). To see the lower bound, assume that \(G=K_{2n-1}\cup {\overline{K}}_{t-1}\). It is clear that there is a blue/red coloring of \(E(K_{2n-1})\) such that there is no blue copy \(C_{2n}\) and no red copy \(P_{3}\). We can take this coloring and we color the edges of \({\overline{G}}={\overline{K}}_{2n-1}+ K_{t-1}\) with color green. There is no green copy \(tK_{2}\).

3.5 \(R(tK_{2},C_{2m},C_{4})\)

Theorem 11

[19] \(b(C_{2m},C_{4})=m+1\) for \(m\ge 4.\)

Theorem 12

[9] \(R(tK_{2},C_{n})=max \lbrace n+2t-1- \lfloor n/2 \rfloor , n+t-1 \rbrace \) for \(n\ge 3.\)

Theorem 13

For a positive integer \(m\ge 4,\)

  1. 1.

    if \(t \ge m+1\) then \(R(tK_{2},C_{2m},C_{4})=m+2t,\)

  2. 2.

    if \(t \le m\) then \(2m+t \le R(tK_{2},C_{2m},C_{4})\le 2m+t+1\).

Proof

(1) By Corollary 1 and Theorem 11, we have \(R(tK_{2},C_{2m},C_{4})\le b+2t-1=m+2t\) where \(b=b(C_{2m},K_{2,2})\) and \(t \ge m+1\). To see the lower bound, consider the graph \(G=K_{R-1}\cup K_{1}\) where \(R=R(tK_{2},C_{2m})=m+2t-1\) for \(t \ge m+1\). It is clear that there is a blue/red coloring of \(E(K_{R-1})\) such that there is no blue copy of \(tK_{2}\) and no red copy of \(C_{2m}\). We can take this coloring. We color the edges of \({\overline{G}}={\overline{K}}_{R-1}+ {\overline{K}}_{1}\) by green. So there is no green copy of \(C_{4}\).

(2) By Corollary 1, we have \(R(tK_{2},C_{2m},C_{4})\le 2b+t-1\) where \(b=b(C_{2m},K_{2,2})\) and \(t\le m+1\). By Theorem 11, we obtain \(R(tK_{2},C_{2m},C_{4})\le 2m+t+1\). To see the lower bound, consider the graph \(G=K_{R-1}\cup K_{1}\) where \(R=R(tK_2,C_{2m})=2m+t-1\). It is clear that there is a blue/red coloring of \(E(K_{R-1})\) such that there is no blue copy of \(tK_{2}\) and no red copy \(C_{2m}\). We can take such a coloring and we color the edges of \({\overline{G}}={\overline{K}}_{R-1}+ {\overline{K}}_{1}\) with green. There is no green copy of \(C_4\) and the proof is complete.

3.6 Multicolor Ramsey Numbers

This last subsection contains some results for Ramsey numbers with more than 3 colors.

Theorem 14

Let \(m_{1}, m_{2},\ldots ,m_{s}\) and \(k_{1}, k_{2}, \ldots , k_{t}\) be positive integers and \(n> n_{1}(b)\) where \(b=b(K_{1,k_{1}}, K_{1,k_{2}}, \ldots , K_{1,k_{t}}, m_{1}K_{2}, m_{2}K_{2}, \ldots , m_{s}K_{2})\). Then

$$\begin{aligned} R(C_n,K_{1,k_{1}},K_{1,k_{2}}, \ldots ,K_{1,k_{t}}, m_{1}K_{2}, m_{2}K_{2}, \ldots , m_{s}K_{2})\le n+b-1. \end{aligned}$$

Proof

By using the same argument as in Theorem 2, we have \(R(C_n,K_{1,k_{1}}, K_{1,k_{2}},\)\(\ldots , K_{1,k_{t}}, m_{1}K_{2}, m_{2}K_{2}, \ldots , m_{s}K_{2}) \le R(C_n,K_{b,b})\) where \(b=b(K_{1,k_{1}}, K_{1,k_{2}},\)\(\ldots , K_{1,k_{t}}, m_{1}K_{2}, m_{2}K_{2}, \ldots , m_{s}K_{2})\). Next we apply Theorem 3.

Lemma 2

[16] Let \(m_{1}, m_{2},\ldots ,m_{s}\) and \(k_{1}, k_{2}, \ldots , k_{t}\) be positive integers with \(\varLambda =\sum _{i=1}^{s}(m_{i}-1)\) and \(\sum =\sum _{i=1}^{t}(k_{i}-1)\). Then \(b(K_{1,k_{1}}, K_{1,k_{2}}, \ldots , K_{1,k_{t}}, m_{1}K_{2}, m_{2}K_{2},\)\(\ldots , m_{s}K_{2})=b,\) where

$$\begin{aligned} b = {\left\{ \begin{array}{ll} \varLambda +1 &{} \text {if } \varSigma <\lfloor (\varLambda +1)/2 \rfloor , \\ \varSigma +\lfloor \varLambda /2 \rfloor +1 &{} \text {if } \varSigma \ge \lfloor (\varLambda +1)/2 \rfloor . \end{array}\right. } \end{aligned}$$

Combining Theorem 14 and Lemma 2, we obtain the following.

Theorem 15

Let \(m_{1}, m_{2},\ldots ,m_{s}\) and \(k_{1}, k_{2}, \ldots , k_{t}\) be positive integers with \(\varLambda =\sum _{i=1}^{s}(m_{i}-1)\) and \(\sum =\sum _{i=1}^{t}(k_{i}-1)\). If \(\varSigma \le \lfloor (\varLambda +1)/2 \rfloor \) for \(n> n_{1}(\varLambda ),\) then

$$\begin{aligned} R(C_n,m_{1}K_{2},m_{2}K_{2},\ldots ,m_{s}K_{2},K_{1,k_{1}},K_{1,k_{2}},\ldots ,K_{1,k_{t}})= n+\varLambda . \end{aligned}$$

Proof

For the upper bound, we apply Theorem 14 and Lemma 2.

For the lower bound color all edges of \(G=K_{n-1}\cup {\overline{K}}_{\varLambda }\) by color 1 and for all edges of \({\overline{G}}={\overline{K}}_{n-1}+ K_{\varLambda }\) consider the following coloring. Color \({\overline{K}}_{n-1}+ K_{m_{1}-1}\) and \({\overline{K}}_{m_{1}-1}+{\overline{K}}_{\sum _{i=2}^{s}(m_{i}-1)}\) by color 2 and color \({\overline{K}}_{n-1}+ K_{m_{2}-1}\) and \({\overline{K}}_{m_{2}-1}+{\overline{K}}_{\sum _{i=3}^{s}(m_{i}-1)}\) by color 3 and in the general color \({\overline{K}}_{n-1}+ K_{m_{j}-1}\) and \({\overline{K}}_{m_{j}-1}+{\overline{K}}_{\sum _{i=j+1}^{s}(m_{i}-1)}\) by color \(j+1\) where \( j\ge 1\) and finally color \({\overline{K}}_{n-1}+ K_{m_{s}-1}\) by color s. Then \(G^{1}\) contains no copy of \(C_{n}\), \(G^{i+1}\) contains no copy of \(m_{i}K_{2}\) for \(1\le i \le s\), as desired. Note that this lower bound is usable on arbitrary graphs \( H_{1},\ldots , H_{t}\) instead of \(K_{1,k_{1}},K_{1,k_{2}},\ldots ,K_{1,k_{t}}\).

Corollary 4

For given positive integers \(m_{1}, m_{2},\ldots ,m_{s}\) and \(k_{1},k_{2},\ldots ,k_{t}\) with \(\varLambda =\sum _{i=1}^{s}(m_{i}-1),\)\(\sum =\sum _{i=1}^{t}(k_{i}-1),\) sufficiently large n and \(\varSigma \le \lfloor (\varLambda +1)/2 \rfloor ,\)

$$\begin{aligned} R(P_{n},K_{1,k_{1}},K_{1,k_{2}},\ldots ,K_{1,k_{t}},m_{1}K_{2},m_{2}K_{2},\ldots ,m_{s}K_{2}) =n+\varLambda . \end{aligned}$$

Lemma 3

[16] For positive integers \(m, k_{1},\ldots ,k_{r}\ge 2\) and \(\sum =\sum _{i=1}^{r}(k_{i}-1),\)

$$\begin{aligned} b(P_{m},K_{1,k_{1}},\ldots ,K_{1,k_{r}})= {\left\{ \begin{array}{ll} \varSigma + \frac{m}{2} &{} \text {if } \varSigma \ge \frac{m}{2}, m\text { even,}\\ \varSigma + \frac{m+1}{2}&{} \text {if } \varSigma \ge \frac{m-1}{2}, m\text { odd, } \varSigma \equiv 0 \text { mod}(\frac{m-1}{2}),\\ \varSigma + \frac{m-1}{2} &{} \text {if } \varSigma \ge \frac{m-1}{2}, m\text { odd, } \varSigma \not \equiv 0 \text { mod}(\frac{m-1}{2}),\\ 2\varSigma +1 &{} \text {if } \frac{1}{2}\lfloor \frac{m}{2} \rfloor +1 \le \varSigma< \lfloor \frac{m}{2} \rfloor +1,\\ \lfloor \frac{m+1}{2} \rfloor &{} \text {if } \varSigma < \frac{1}{2}\lfloor m/2 \rfloor . \end{array}\right. } \end{aligned}$$

Theorem 16

For \( \varSigma <\frac{s}{2},\)\(m=2s\) and \(2 \le t\le s,\)

$$\begin{aligned} R(tK_{2},P_{m},K_{1,k_{1}},\ldots ,K_{1,k_{r}})=m+t-1. \end{aligned}$$

Proof

Suppose that \( \varSigma < \frac{s}{2}\), \(m=2s\) and \(2 \le t\le s\). By Corollary 1 and Lemma 3, we have \(R(tK_{2},P_{m},K_{1,k_{1}},\ldots ,K_{1,k_{r}})\le m+t-1 \). To obtain the lower bound, divide the vertex set of \(G=K_{m+t-2}\) into two parts A and B, where \(|A|=m-1\) and \(|B|=t-1\). Color the edges of G[A] with the second color and other edges with the first color. Note that the lower bound is usable for arbitrary graphs \( H_{1},\ldots , H_{t}\) instead of \(K_{1,k_{1}},K_{1,k_{2}},\ldots ,K_{1,k_{r}}\).