1 Introduction
Given two simple graphs and . We use the notation ⟶ ሺ, ሻ when for any red-blue coloring of the edges of a graph we always have a red subgraph or a blue subgraph . The Ramsey number ሺ, ሻ is defined as the smallest positive integer n such that ⟶ ሺ, ሻ, where is the complete graph on n vertices. Some values of the Ramsey number for a combination of a star and a path were determined by Parsons [1]. One year before, the multicolor Ramsey number for stars was determined by Burr and Roberts [2]. Then, the concept of Ramsey numbers evolved to the bipartite Ramsey number ሺ, ሻ, which is defined as the smallest positive integer n such that , ⟶ ሺ, ሻ. In 1998, the bipartite Ramsey number for a star and a path was completed by Hattingh and Henning [3].
Furthermore, in 2004 Burger and Vuuren [4] generalized the concept of bipartite Ramsey numbers to the size multipartite Ramsey numbers as follows. Let j, l, n, r and s be natural numbers with , 2. The size multipartite Ramsey number ሺൈ, ൈ௦ሻ is the smallest natural number t such that an arbitrary red-blue coloring of the edges of ൈ௧, where ൈ௧ is the complete multipartite graph having j partite sets with t vertices per each partite set, necessarily forces a red ൈ or a blue ൈ௦ as a subgraph. They also gave some
Received December 5th, 2018, Revised October 23rd, 2019, Accepted for publication October 29th, 2019. Copyright © 2020 Published by ITB Institute for Research and Community Services, ISSN: 2337-5760, DOI: 10.5614/j.math.fund.sci.2020.52.1.1
properties of the size multipartite Ramsey numbers and determined the exact values of \(m_j(K_{2\times 2}, K_{3\times 1})\), for \(j \ge 2\). For the bounds of the size multipartite Ramsey numbers they gave a direct lower bound, a probabilistic lower bound, and a diagonal bipartite upper bound.
Syafrizal, et al. [5] generalized this concept by removing the completeness requirement. Thus, the size multipartite Ramsey number, \(m_j(G, H)\), is defined as the smallest positive integer t such that \(K_{j \times t} \to (G, H)\). They also determined the size multipartite Ramsey numbers for paths and other graphs [5,6], especially the size multipartite Ramsey numbers for \(P_3\) and stars [7]. Then, Surahmat and Syafrizal [8] gave the size tripartite Ramsey numbers for paths \(P_n\) and stars, for \(1 \le n \le n\) decreased by Lusiani, et al. [9]. They also provided the size tripartite Ramsey numbers for \(P_3\) and a disjoint union of homogeneous stars [10] and the size tripartite Ramsey numbers for stars with paths and cycles [11]. Recently, Jayawardene and Samarasekara [12] determined the size multipartite Ramsey numbers for \(P_3\) and all graphs up to 4 vertices, including the star of order 4. However, the multipartite Ramsey numbers for \(P_3\) and a disjoint union of heterogeneous stars have not been determined.
Here, the generalized concept of the size multipartite Ramsey numbers for a star forest and \(P_3\) is used. The star forest is a disjoint union of heterogeneous stars. In this paper, we determine the size multipartite Ramsey numbers \(m_j(\bigcup_{i=1}^k K_{1,n_i}, P_3)\), for j=2,3, where \(\bigcup_{i=1}^k K_{1,n_i}\) is a star forest, for \(n_i \ge 1, k \ge 2\) and \(P_3\) is a path on 3 vertices. For k=1, Hattingh and Henning [3] determined \(m_2(K_{1,r}, P_s)\), for \(r, s \ge 2\).
For some terms in graph theory used in this paper, we refer to Chartrand [13]. Let G be a finite and simple graph. The vertex and edge sets of graph G are denoted by V(G) and E(G), respectively. A matching of a graph G is defined as the set of edges without a common vertex. Let \(e = u \sim v\) be an edge in G, then G is called adjacent to G. The neighborhood G is a vertex G is the set of vertices adjacent to G in G. The degree G is a vertex G is G is length of a vertex G is G in the maximum degree of G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted by G is denoted
2 Bipartite Ramsey Numbers
In this section, we discuss the size bipartite Ramsey number \(m_2(\bigcup_{i=1}^k K_{1,n_i}, P_3)\), for \(k \ge 2\) and \(n_i \ge 1\). We compute the formula of this Ramsey number for any \(k \ge 2\) and \(n_i \ge 1\). In particular, for \(n_i = 1\), for all i, we obtain the value of \(m_2(kK_{1,1}, P_3) = m_2(kP_2, P_3)\), correcting the previous result given by Christou, et al. [14]. They showed that \(m_2(kP_2, K_{1,n}) = n + \left\lfloor \frac{k-1}{2} \right\rfloor\), for \(k \ge 2\) and \(n \ge 1\). For n = 2, they had \(m_2(kP_2, P_3) = 2 + \left\lfloor \frac{k-1}{2} \right\rfloor\), which is not correct for \(k \ge 4\).
Lemma 2.1 \[m_2(kP_2, P_3) = \begin{cases} 2, & \text{for } k = 1 \\ k, & \text{for } k \ge 2 \end{cases}\]
Proof. Let \[t = \begin{cases} 2, & \text{for } k = 1 \\ k, & \text{for } k \ge 2 \end{cases}\]
We consider the coloring of \(K_{2\times(t-1)}=F_R\oplus F_B\), such that \(F_B\) does not contain \(P_3\). So, \(\Delta(F_B)\leq 1\). This is trivial for k=1 since \(F_B=K_2\) and \(F_R\) is an empty graph. For \(k\geq 2\), we choose \(F_B=(k-1)P_2\). In this case, we will have no \(kP_2\) in \(F_R\) and \(F_B\not\supseteq P_3\). So, \(m_2(kP_2,P_3)\geq t\).
Now, we show that \(m_2(kP_2,P_3) \le t\). We consider any coloring of \(K_{2\times t} = G_R \oplus G_B\), such that \(G_B\) does not contain a blue \(P_3\), so \(\Delta(G_B) \le 1\). For k=1, we have \(K_{2\times 2} = G_R \oplus G_B\). So, \(G_B\) is either a matching graph or an empty graph and \(G_R\) is either \(2P_2, P_4\) or \(C_4\), which implies \(G_R \supseteq 2P_2\). For \(k \ge 2\), we have \(K_{2\times k} = G_R \oplus G_B\). Let \(U = \{u_1, u_2, ..., u_k\}\) and \(V = \{v_1, v_2, ..., v_k\}\) be two partite sets in \(K_{2\times k}\). If \(G_B\) is a matching graph, then every vertex in \(K_{2\times k}\) is relabeled such that \(u_i \sim v_i\) in \(G_B\), for every i=1,2,...,k. We consider a cycle in \(K_{2\times k}\), namely \(C_k' = u_1v_1u_2v_2u_3v_3 ... u_kv_ku_1\). So, \(E(C_k') - E(G_B)\) contains a red \(kP_2\). Therefore, \(G_R\) contains a red \(kP_2\).
In Lemma 2.1 we obtain the size bipartite Ramsey number, \(m_2(\bigcup_{i=1}^k K_{1,n_i}, P_3)\), for \(n_i = 1\), for all i. So, in Theorems 2.2, 2.4 and 2.5, we determine the size bipartite Ramsey numbers \(m_2(\bigcup_{i=1}^k K_{1,n_i}, P_3)\), for all \(n_i \ge 1\), for \(1 \le k \le 4\). For a combination of two stars and \(1 \le k \le 4\).
Theorem 2.2 Let \(n_1\) and \(n_2\) be positive integers. Then, \(m_2(K_{1,n_1} \cup K_{1,n_2}, P_3) = \max\{n_1, n_2\} + 1\).
Proof. Let \(n_1 \ge n_2 \ge 1\), so we have \(\max\{n_1, n_2\} + 1 = n_1 + 1\). To show that \(m_2(K_{1,n_1} \cup K_{1,n_2}, P_3) \ge n_1 + 1\), we consider the coloring of \(K_{2 \times n_1} = F_R \oplus F_B\), such that \(F_B\) does not contain \(P_3\). So, \(\Delta(F_B) \le 1\). We can choose \(F_B = F_B\)
\(n_1P_2\). Let \(U=\{u_1,u_2,...,u_{n_1}\}\) and \(V=\{v_1,v_2,...,v_{n_1}\}\) be two partite sets in \(K_{2\times n_1}\). Every vertex in \(K_{2\times n_1}\) is relabeled such that \(u_i\sim v_i\) in \(F_B\), for every \(i=1,2,...,n_1\). Since \(u_i\sim v_j\) in \(F_R\), for \(i\neq j\), so \(F_R\) does not contain \(K_{1,n_1}\). Therefore, \(m_2(K_{1,n_1}\cup K_{1,n_2},P_3)\geq n_1+1\).
Figure 1 (a). \(G_B = pK_2\), for \(1 \le p \le n + 1\) (b). \(2K_{1,n_1} \subseteq G_R \subseteq K_{2 \times (n_1 + 1)}\).
Now, we show that \(m_2(K_{1,n_1} \cup K_{1,n_2}, P_3) \le n_1 + 1\). We consider any coloring of \(K_{2\times(n_1+1)} = G_R \oplus G_B\), such that \(G_B\) does not contain a blue \(P_3\), so \(\Delta(G_B) \le 1\). Let \(U = \{u_1, u_2, \dots, u_{n_1+1}\}\) and \(V = \{v_1, v_2, \dots, v_{n_1+1}\}\) be two partite sets in \(K_{2\times(n_1+1)}\). If \(G_B\) is a matching graph, then every vertex in \(K_{2\times(n_1+1)}\) is relabeled such that \(u_i \sim v_i\) in \(F_B\), for any \(i = 1, 2, \dots, n_1 + 1\), see Figure 1(a). Since \(u_1 \sim v_j\) and \(v_1 \sim u_j\) in \(G_R\), for \(1 \le i\), \(1 \le i\), \(1 \le i\), we find a disjoint union of stars \(1 \le i\), see Figure 1(b).
For the proofs of Theorems 2.4 and 2.5, we use Lemma 2.3, which is stated as follows. Note that we previously defined \(sum(A) = \sum_{i=1}^{k} n_i\), for \(A = \{n_1, n_2, ..., n_k\}\).
Lemma 2.3 Let \(N = \{n_1, n_2, ..., n_k\}\), for \(k \ge 2\) and \(n_1 \ge n_2, \ge ... \ge n_k \ge 1\). For \(1 \le i \le 2^k\), let \(A \in \mathcal{P}(N)\), where \(A_i \ne A_j\), for \(i \ne j\). Let \(B_i = N - A_i\), and \(L_i = \max\{\text{sum}(A_i) + |B|, \text{sum}(B_i) + |A|\}\). There exists \(p \in \{1, 2, 3, ..., 2^k\}\), where \(A_p\) or \(B_p\) is not empty (or \(A_p\) or \(B_p\) is not N), such that \(L_k = \min\{L_i | 1 \le i \le 2^k\}\).
Proof. Let \(A_r = \emptyset\) and \(B_r = N\), for any \(r \in \{1,2,3,...,2^k\}\). Then \(L_r = \max\{\text{sum}(A_r) + |B_r|, \text{sum}(B_r) + |A_r|\} = \text{sum}(N)\). Let us consider \(A_s\), where \(|A_s| \ge 1\) and \(B_s = N - A_s\), where \(|B_s| \ge 1\). We assume that \(|A_s| = t \ge 1\).
Then \(L_s = \max\{\text{sum}(A_s) + k - t, \text{sum}(B_s) + t\}\). Note that \(\text{sum}(N) = \text{sum}(A_s) + \text{sum}(B_s) \ge \text{sum}(A_s) + k - t\) and \(\text{sum}(N) = \text{sum}(A_s) + \text{sum}(B_s) \ge t + \text{sum}(B_s)\). So, if \(A_s = \{1\}\), then \(L_s = L_r\). Otherwise, \(L_s < L_r\). Then, \(L = \min(L_s) < L_r\). Therefore, L is minimum when A and B are not empty.
Theorem 2.4 Let \(N = \{n_1, n_2, n_3\}\) be the set of the number of leaves of three stars \(K_{1,n_1}\), \(K_{1,n_2}\) and \(K_{1,n_3}\), respectively. If \(L = \{\max\{\text{sum}(A) + |B|, \text{sum}(B) + |A|\}|A, B \subseteq N, A \cup B = N, A \cap B = \emptyset\}\), then \(m_2(\bigcup_{i=1}^3 K_{1,n_i}, P_3) = \min(L)\).
Proof. Let \(n_1 \ge n_2 \ge n_3 \ge 1\). We have \(L = \{n_1 + n_2 + n_3, \max\{n_1 + 2, n_2 + n_3 + 1\}, n_1 + n_2 + 1, n_1 + n_3 + 1\}\). By Lemma 2.2, \(L = \{\max\{n_1 + 2, n_2 + n_3 + 1\}, n_1 + n_2 + 1, n_1 + n_3 + 1\}\). Therefore, \(\min(L) = \max\{n_1 + 2, n_2 + n_3 + 1\}\).
Let \(t = \max\{n_1 + 2, n_2 + n_3 + 1\}\). To show that \(m_2(\bigcup_{i=1}^3 K_{1,n_i}, P_3) \ge t\), we consider the coloring of \(K_{2\times(t-1)} = F_R \oplus F_B\), such that \(F_B\) does not contain a blue \(P_3\), so \(\Delta(F_B) \le 1\). We can choose that \(F_B = (t-1)P_2\). Let \(U = \{u_1, u_2, ..., u_{t-1}\}\) and \(V = \{v_1, v_2, ..., v_{t-1}\}\) be two partite sets in \(K_{2\times(t-1)}\). Every vertex in \(K_{2\times(t-1)}\) is relabeled such that \(u_i \sim v_i\) in \(F_B\), for any i = 1, 2, ..., t-1. We have the following two possibilities for the values of t-1:
- 1. For \(t-1=n_1+1\). Since \(u_1 \sim v_j\), for \(2 \leq j \leq n_1+1\) in \(F_R\), the star \(K_{1,n_1}\) can be constructed by these vertices. Since \(v_1 \sim u_i\), for \(2 \leq i \leq n_2+1 \leq n_1+1\) in \(F_R\), the star \(K_{1,n_2}\) can be constructed by vertices \(v_1,u_2,u_3,\ldots,u_{n_2+1}\). However, we cannot construct the star \(K_{1,n_3}\), since we cannot choose any of the remaining vertices as its center.
- 2. For \(t-1=n_2+n_3\). Since \(u_1 \sim v_j\), for \(n_2+1 \leq n_2+n_3\) in \(F_R\), the star \(K_{1,n_3}\) can be constructed by these vertices. Since \(u_{n_2+1} \sim v_j\), for \(1 \leq j \leq n_2\) in \(F_R\), the star \(K_{1,n_2}\) can be constructed by these vertices. However, we cannot construct the star \(K_{1,n_1}\), since we cannot choose any of the remaining vertices as its center.
\(F_R\) does not contain all stars \(K_{1,n_1}\), \(K_{1,n_2}\) and \(K_{1,n_3}\), so \(F_R\) does not contain \(\bigcup_{i=1}^3 K_{1,n_i}\).
Now, we show that \(m_2(\bigcup_{i=1}^3 K_{1,n_i}, P_3) \le t\). We consider any coloring of \(K_{2\times t} = G_R \oplus G_B\), such that \(G_B\) does not contain a blue \(P_3\), so \(\Delta(G_B) \le 1\). Then
\(G_B\) is a matching graph. Let \(U = \{u_1, u_2, ..., u_t\}\) and \(V = \{v_1, v_2, ..., v_t\}\) be two partite sets in \(K_{2 \times t}\). Every vertex in \(K_{2 \times t}\) is relabeled such that \(u_i \sim v_j\) in \(G_B\), for some i = j. We have the following two possibilities for the values of t:
- 1. For \(t = n_1 + 2\)Since \(u_1 \sim v_j\), for \(3 \leq j \leq n_1 + 2\) in \(G_R\), the star \(K_{1,n_1}\) can be constructed by these vertices. Since \(v_1 \sim u_2\) and \(v_1, v_2\) are both adjacent to \(u_i\) for \(3 \leq i \leq n_1 + 2\) in \(G_R\), the star \(K_{1,n_2}\) can be constructed by vertices \(v_1, u_2, u_3, \dots, u_{n_2+1}\), and the star \(K_{1,n_3}\) can be constructed by vertices \(v_2, u_{n_2+2}, u_{n_2+3}, \dots, u_{n_3+n_2+1}\).
- 2. For \(t = n_2 + n_3 + 1\)Since \(u_1 \sim v_j\), for \(3 \leq j \leq n_2 + n_3 + 1\) in \(G_R\), the star \(K_{1,n_1}\) can be constructed by vertices \(u_1, v_3, v_4, \dots, v_{n_1+2}\). Since \(v_1 \sim u_2\) and \(v_1, v_2\) are both adjacent to \(u_i\) for \(3 \leq i \leq n_2 + n_3 + 1\) in \(G_R\), the star \(K_{1,n_2}\) can be constructed by vertices \(v_1, u_2, u_3, \dots, u_{n_2+1}\) and the star \(K_{1,n_3}\) can be constructed by vertices \(v_2, u_{n_2+2}, u_{n_2+3}, \dots, u_{n_2+n_2+1}\).
Therefore, \(G_R\) contains \(\bigcup_{i=1}^3 K_{1,n_i}\).
Theorem 2.5 Let \(N = \{n_1, n_2, n_3, n_4\}\) be the set of the number of leaves of three stars \(K_{1,n_1}, K_{1,n_2}, K_{1,n_3}\) and \(K_{1,n_4}\), respectively. If \(L = \{\max\{\text{sum}(A) + |B|, \text{sum}(B) + |A|\}|A, B \subseteq N, A \cup B = N, A \cap B = \emptyset\}\), then \(m_2(\bigcup_{i=1}^4 K_{1,n_i}, P_3) = \min(L)\).
Proof. Let \(n_1 \ge n_2 \ge n_3 \ge n_4 \ge 1\). We have \(L = \{n_1 + n_2 + n_3 + n_4, \max\{n_1 + 3, n_2 + n_3 + n_4 + 1\}, n_1 + n_2 + 2, n_3 + n_4 + 2, n_1 + n_2 + n_3 + 1, n_1 + n_2 + n_4 + 1, n_1 + n_3 + n_4 + 1, \max\{n_1 + n_4 + 2, n_2 + n_3 + 2\}\}.\)
By Lemma 2.2,
\[L = \{ \max\{n_1+3, n_2+n_3+n_4+1\}, n_1+n_2+2, n_3+n_4+2, n_1+n_2+n_3+1, n_1+n_2+n_4+1, n_1+n_3+n_4+1, \max\{n_1+n_4+2, n_2+n_3+2\}\}.\]
Therefore.
\(\min(L) = \min\{\max\{n_1 + 3, n_2 + n_3 + n_4 + 1\}, \max\{n_1 + n_4 + 2, n_2 + n_3 + 2\}\}.\) Then, we have three following possibilities for \(\min(L)\):
- 1. If \(n_1 > n_2 + n_3\), then \(\min(L) = \min(L') = \max\{n_1 + 3, n_2 + n_3 + n_4 + 1\}\).
- 2. If \(n_1 < n_2 + n_3\), then \(\min(L) = \min(L'') = \max\{n_1 + n_4 + 2, n_2 + n_3 + 2\}\).
- 3. If \(n_1 = n_2 + n_3\), then min(L) = min(L') or min(L) = min(L").
Let \(t = \min(L)\). To show that \(m_2(\bigcup_{i=1}^4 K_{1,n_i}, P_3) \ge t\) we consider the coloring of \(K_{2\times(t-1)} = F_R \oplus F_B\), such that \(F_B\) does not contain a blue \(P_3\), so \(\Delta(F_B) \le 1\).
We can choose that \(F_B = (t-1)P_2\). Let Let \(U = \{u_1, u_2, \dots, u_{t-1}\}\) and \(V = \{v_1, v_2, \dots, v_{t-1}\}\) be two partite sets in \(K_{2\times(t-1)}\). Every vertex in \(K_{2\times(t-1)}\) is relabeled such that \(u_i \sim v_i\) in \(F_B\), for every \(i = 1, 2, \dots, t-1\). We have four possibilities for the values of t-1, as follows:
- 1. For \(t-1=\min(L')-1=n_1+2\)Since \(u_1 \sim v_j\), for \(2 \leq j \leq n_1+1\) in \(F_R\), the star \(K_{1,n_1}\) can be constructed by these vertices. Since \(v_1 \sim u_i\), for \(n_2+2 \leq i \leq n_2+n_3+1 \leq n_1+1\) in \(F_R\), the star \(K_{1,n_2}\) and \(K_{1,n_3}\) can be constructed by vertices \(v_1, u_2, u_3, \dots, u_{n_2+1}\) and \(v_{n_1+2}, u_{n_2+2}, u_{n_2+3}, \dots, u_{n_3+n_2+1}\), respectively. However, we cannot construct the star \(K_{1,n_4}\), since we cannot choose any of the remaining vertices as its center.
- 2. For \(t-1=\min(L')-1=n_2+n_3+n_4\)Since \(u_1 \sim v_j\), for \(2 \leq j \leq n_2+1\) in \(F_R\), the star \(K_{1,n_2}\) can be constructed by these vertices. Since \(u_2 \sim v_j\), for \(n_2+2 \leq j \leq n_2+n_3+1\) in \(F_R\), the star \(K_{1,n_3}\) can be constructed by these vertices. Since \(u_3 \sim v_j\), for j=1 and \(n_2+n_3+2 \leq j \leq n_2+n_3+n_4\) in \(F_R\), the star \(K_{1,n_4}\) can be constructed by these vertices. However, we cannot construct the star \(K_{1,n_1}\), since we cannot choose any of the remaining vertices as its center.
- 3. For \(t-1=\min(L'')-1=n_1+n_4+1\)Since \(u_1\sim v_j\), for \(2\leq j\leq n_1+1\) in \(F_R\), the star \(K_{1,n_1}\) can be constructed by these vertices. Since \(u_2\sim v_j\), for \(n_1+2\leq j\leq n_1+n_4+1\) in \(F_R\), the star \(K_{1,n_4}\) can be constructed by these vertices. Since \(v_1\sim u_i\), for \(1\leq i\leq n_2+1\) in \(1\leq i\leq n_2+1\) in \(1\leq i\leq n_3+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\leq n_4+1\) in \(1\leq i\)
- 4. For \(t-1=\min(L'')-1=n_2+n_3+1\)Since \(u_1 \sim v_j\), for \(2 \leq j \leq n_2+1\) in \(F_R\), the star \(K_{1,n_2}\) can be constructed by these vertices. Since \(u_2 \sim v_j\), for \(n_2+2 \leq j \leq n_2+n_3+1\) in \(F_R\), the star \(K_{1,n_3}\) can be constructed by these vertices. Since \(v_1 \sim u_i\), for \(1 \leq i \leq n_1+2\) in \(1 \leq i \leq n_2+n_3\), the star \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq n_3+2\) in \(1 \leq i \leq n_3+2\) in \(1 \leq n_3+2\) in \(1 \leq n_3+2\) in \(1 \leq n\)
Since \(F_R\) does not contain all stars \(K_{1,n_1}, K_{1,n_2}, K_{1,n_3}\) and \(K_{1,n_4}\), therefore \(F_R\) does not contain \(\bigcup_{i=1}^4 K_{1,n_i}\).
Now we show that \(m_2(\bigcup_{i=1}^4 K_{1,n_i}, P_3) \le t\). We consider any coloring of \(K_{2\times t} = G_R \oplus G_B\), such that \(G_B\) does not contain a blue \(P_3\), so \(\Delta(G_B) \le 1\). Then \(G_B\) is a matching graph. Let \(U = \{u_1, u_2, ..., u_t\}\) and \(V = \{v_1, v_2, ..., v_t\}\) be two
partite sets in \(K_{2\times t}\). Every vertex in \(K_{2\times t}\) is relabeled such that \(u_i \sim v_i\) in \(G_B\), for any i = 1, 2, ..., t. There are four possibilities for the values of t, as follows.
- 1. For \(t = \min(L') = n_1 + 3\)Since \(u_1 \sim v_j\), for \(2 \leq j \leq n_1 + 1\) in \(G_R\), the star \(K_{1,n_1}\) can be constructed by these vertices. Since \(v_j \sim u_i\) for \(j = 1, n_1 + 2, n_1 + 3\) and \(2 \leq i \leq n_2 + 1\) in \(G_R\), the star \(K_{1,n_2}\), \(K_{1,n_3}\) and \(K_{1,n_4}\) can be constructed by vertices \(\{v_1, u_2, u_3, \dots, u_{n_2+1}\}\), \(\{v_{n_1+2}, u_{n_2+2}, u_{n_2+3}, \dots, u_{n_2+n_3+1}\}\) and \(\{v_{n_1+3}, u_{n_2+n_3+2}, u_{n_2+n_3+3}, \dots, u_{n_2+n_3+n_4+1}\}\), respectively.
- 2. For \(t = \min(L') = n_2 + n_3 + n_4 + 1\)Since \(v_1 \sim u_i\), for \(4 \le i \le n_1 + 3\) in \(G_R\), the star \(K_{1,n_1}\) can be constructed by these vertices. Since \(v_j \sim u_i\) for i = 1, 2, 3 and \(2 \le j \le n_2 + n_3 + n_4 + 1\) in \(G_R\), the star \(K_{1,n_2}\), \(K_{1,n_3}\) and \(K_{1,n_4}\) can be constructed by vertices \(\{u_1, v_2, v_3, ..., v_{n_2+1}\}\), \(\{u_2, v_{n_2+2}, v_{n_2+3}, ..., v_{n_2+n_3+1}\}\) and \(\{u_3, v_{n_2+n_3+2}, v_{n_2+n_3+3}, ..., v_{n_2+n_3+n_4+1}\}\), respectively.
- 3. For \(t = \min(L'') = n_1 + n_4 + 2\)Since \(u_i \sim v_j\), for i = 1,2 and \(2 \leq j \leq n_1 + n_4 + 1\) in \(G_R\), the star \(K_{1,n_1}\) and \(K_{1,n_4}\) can be constructed by vertices \(u_1, v_2, v_3, \dots, v_{n_1+1}\) and \(u_2, v_{n_1+2}, v_{n_1+3}, \dots, v_{n_1+n_4+1}\). Since \(v_j \sim u_i\), for \(3 \leq i \leq n_2 + n_3 + 2\) and \(j = 1, n_1 + n_4 + 2\) in \(G_R\), the star \(K_{1,n_2}\) and \(K_{1,n_3}\) can be constructed by vertices \(\{v_{n_1+n_4+2}, u_3, u_4, \dots, u_{n_2+2}\}\) and \(\{v_1, u_{n_2+3}, u_{n_2+4}, \dots, u_{n_2+n_3+2}\}\), respectively.
- 4. For \(t = \min(L'') = n_2 + n_3 + 2\)Since \(u_i \sim v_j\), for i = 1,2 and \(2 \leq j \leq n_2 + n_3 + 1\) in \(G_R\), the star \(K_{1,n_2}\) and \(K_{1,n_3}\) can be constructed by vertices \(u_1, v_2, v_3, \dots, v_{n_2+1}\) and \(u_2, v_{n_2+2}, v_{n_2+3}, \dots, v_{n_2+n_3+1}\). Since \(v_j \sim u_i\), for \(3 \leq i \leq n_1 + n_4 + 2\) and \(j = 1, n_2 + n_3 + 2\) in \(G_R\), the star \(K_{1,n_1}\) and \(K_{1,n_4}\) can be constructed by vertices \(\{v_{n_2+n_3+2}, u_3, u_4, \dots, u_{n_1+2}\}\) and \(\{v_1, u_{n_1+3}, u_{n_1+4}, \dots, u_{n_1+n_4+2}\}\), respectively.
Therefore, \(G_R\) contains \(\bigcup_{i=1}^4 K_{1,n_i}\).
From Theorems 2.4 and 2.5, we obtain \(m_2(\bigcup_{i=1}^k K_{1,n_i}, P_3) = \min(L)\) for \(k \in \{2,3,4\}\). For \(k \geq 5\), it seems that the bipartite Ramsey number for a pair of \(\bigcup_{i=1}^k K_{1,n_i}\) and \(P_3\) is \(\min(L)\). For example, it is easy to see the bipartite Ramsey number for a pair of \(2K_{1,6} \cup 2K_{1,5} \cup K_{1,4} \cup K_{1,3} \cup K_{1,2}\) and \(P_3\). In this case, we calculate that \(\min(L) = 19\). Then, \(m_2(2K_{1,6} \cup 2K_{1,5} \cup K_{1,4} \cup K_{1,3} \cup K_{1,2}, P_3) = 19\), see Figure 2.
Figure 2 A disjoint union of stars \(2K_{1,6} \cup 2K_{1,5} \cup K_{1,4} \cup K_{1,3} \cup K_{1,2}\) in \(K_{2\times 19}\).
Now, we consider another extremal example in Figure 3. Since 100 is too large compared to other numbers of leaves, 100 and the other numbers of leaves are in a different partite set. We calculate that \(\min(L) = 109\). Then, \(m_2(K_{1,100} \cup K_{1,55} \cup 8K_{1,1}, P_3) = 109\). Therefore, we present the following conjecture.
Figure 3 A disjoint union of stars \(K_{1,100} \cup K_{1,55} \cup 8K_{1,1}\) in \(G_R \subseteq K_{2 \times 109}\).
Conjecture 2.1 Let \(N = \{n_1, n_2, n_3, ..., n_k\}\) be the set of the number of leaves of stars \(K_{1,n_i}\), for \(n_i \ge 1\), \(1 \le i \le k\) and \(k \ge 2\), respectively. If \(L = \{\max\{\sup(A) + |B|, \sup(B) + |A|\} |A, B \subseteq N, A \cup B = N, A \cap B = \emptyset\}\), then \(m_2(\bigcup_{i=1}^k K_{1,n_i}, P_3) = \min(L)\).
3 Tripartite Ramsey Numbers
In this section, the size tripartite Ramsey numbers for a star forest and \(P_3\) is investigated.
Theorem 3.1 Let \(n_1 \ge n_2 \ge 1\) be positive integers. Let \(A = \left\lceil \frac{2+n_1+n_2}{3} \right\rceil\) and \(B = \left\lceil \frac{n_1+1}{2} \right\rceil\). Then, \(m_3(K_{1,n_1} \cup K_{1,n_2}, P_3) = \max\{A, B\}\).
Proof. Let \(t = \max\{A, B\}\). To show that \(m_3(K_{1,n_1} \cup K_{1,n_2}, P_3) \ge t\), we consider the two following possibilities for the value of t:
- 1. If \(A \ge B\), then \(t = \left\lceil \frac{2 + n_1 + n_2}{3} \right\rceil\). We make the edges of graph \(K_{3 \times (t-1)}\) red. Since \(\left| V \left( K_{3 \times (t-1)} \right) \right| = 3t 3 = 3 \left\lceil \frac{2 + n_1 + n_2}{3} \right\rceil 3 < 2 + n_1 + n_2 = \left| V \left( K_{1,n_1} \cup K_{1,n_2} \right) \right|\), \(V \left( K_{3 \times (t-1)} \right)\) contains neither a blue \(P_3\) nor the red \(K_{1,n_1} \cup K_{1,n_2}\).
- 2. If A < B, then \(t = \left\lceil \frac{n_1 + 1}{2} \right\rceil\). Suppose that \(m_3 \left( K_{1, n_1} \cup K_{1, n_2}, P_3 \right) < t\). Then, \(n_1 \le 2(t 1) 1 = 2 \left\lceil \frac{n_1 + 1}{2} \right\rceil\), which is a contradiction.
Therefore, \(m_3(K_{1,n_1} \cup K_{1,n_2}, P_3) \ge t\).
Now, we show that \(m_3(K_{1,n_1} \cup K_{1,n_2}, P_3) \le t\). We consider any coloring of \(K_{3\times t} = G_R \oplus G_B\) such that \(G_B\) does not contain a blue \(P_3\). Thus, \(\Delta(G_B) \le 1\) and \(G_B\) is a matching graph. We consider any two endpoints of a \(P_2\) in \(G_B\), say u and v. We know that \(d_{G_R}(u) = d_{G_R}(v) = 2t - 1\). If \(n_1 = 2t - 1 - s\), for some nonnegative integers \(s \le \frac{t}{2}\), then \(n_2 \le t - 1 + s\). Then we always have a disjoint union of two stars \(K_{1,n_1} \cup K_{1,n_2}\) in \(G_R\) with u and v as their centers, respectively, and all vertices that are in the same partite set with v being the leaves of \(K_{1,n_1}\).
Theorem 3.2 Let \(n_1 \ge n_2 \ge n_3 \ge 1\) be positive integers. Let \(A = \left[\frac{3+n_1+n_2+n_3}{3}\right]\) and \(B = \left[\frac{n_1+2}{2}\right]\). Then, \(m_3\left(\bigcup_{i=1}^3 K_{1,n_i}, P_3\right) = \max\{A, B\}\).
Proof. Let \(t = \max\{A, B\}\). To show that \(m_3(\bigcup_{i=1}^3 K_{1,n_i}, P_3) \ge t\), we consider the following two possibilities for the value of t:
- 1. If \(A \ge B\), then \(t = \left\lceil \frac{3 + n_1 + n_2 + n_3}{3} \right\rceil\). We make the edges of graph \(K_{3 \times (t-1)}\) red. Since \(\left| V \left( K_{3 \times (t-1)} \right) \right| = 3t 3 = 3 \left\lceil \frac{3 + n_1 + n_2 + n_3}{3} \right\rceil 3 < 3 + n_1 + n_2 + n_3 = \left| V \left( \bigcup_{i=1}^3 K_{1,n_i} \right) \right|\), \(V \left( K_{3 \times (t-1)} \right)\) contains neither a blue \(P_3\) nor the red \(\bigcup_{i=1}^3 K_{1,n_i}\).
- 2. If A < B, then \(t = \left\lceil \frac{n_1 + 2}{2} \right\rceil\). Suppose that \(m_3 \left( \bigcup_{i=1}^3 K_{1,n_i}, P_3 \right) < t\). Then, \(n_1 \le 2(t-1) 2 = 2 \left\lceil \frac{n_1 + 2}{2} \right\rceil 4 < n_1\), which is a contradiction.
Therefore, \(m_3(\bigcup_{i=1}^3 K_{1,n_i}, P_3) \ge t\).
Now, we show that \(m_3\left(\bigcup_{i=1}^3 K_{1,n_i},P_3\right) \leq t\). We consider any coloring of \(K_{3\times t} = G_R \oplus G_B\), such that \(G_B\) does not contain a blue \(P_3\). Thus, \(\Delta(G_B) \leq 1\) and \(G_B\) is a matching graph. Let \(U = \{u_1,u_2,\ldots,u_t\}, V = \{v_1,v_2,\ldots,v_t\}\) and \(W = \{w_1,w_2,\ldots,w_t\}\) be the three partite sets of graph \(K_{3\times t}\). Let \(E(G_B) \supseteq E(UV) \cup E(VW) \cup E(UW)\), where \(E(UV) = \{u_1v_1,u_2v_2,\ldots,u_pv_p\}\), \(E(VW) = \{v_{p+1}w_1,v_{p+2}w_2,\ldots,v_{p+q}w_q\}\) and
\(E(UW) = \{u_{p+1}w_{q+1}, u_{p+2}w_{q+2}, \dots, u_{p+r}w_{q+r}\}\). Note that \(p+q \le t, q+r \le t\) and \(p+r \le t\). For the values of p,q and r, we have four matching possibilities in \(G_B\):
- 1. \(p \ge 1, q = r = 0\), see Figure 4(a).
- 2. \(p \ge 1\), q = 0, \(r \ge 1\), see Figure 4(b) or \(p \ge 1\), \(q \ge 1\), r = 0, see Figure 4(c).
- 3. \(p \ge 1, q \ge 1, r \ge 1\), see Figure 5.
Figure 4 Three matching possibilities in \(G_B\).
Figure 5 A matching in \(G_R\), if \(p \ge 1\), \(q \ge 1\), \(r \ge 1\).
To show the three stars in \(G_R\), we choose the centers of stars \(K_{1,n_1}, K_{1,n_2}\) and \(K_{1,n_3}\) are \(u_1, v_1\) and either \(v_{p+1}\) (if p < t) or \(w_1\) (if p = t), respectively. If t = A, then \(t = \left\lceil \frac{3+n_1+n_2+n_3}{3} \right\rceil \le \left\lceil \frac{3+3n_1}{3} \right\rceil = 1+n_1\). If t = B, then \(t = \left\lceil \frac{n_1+2}{2} \right\rceil \le n_1+1\). Therefore, \(t-1=n_1\), for all \(n_1, n_2\) and \(n_3\). Then, \(t-1 \le n_1 \le 2t-2\). Let \(s_1 = n_1 - (t-2) \ge 1\), so \(v_2, v_3, \dots, v_p, v_{p+2}, \dots, v_{p+q}, v_{p+q+1}, \dots, v_t, w_1, w_2, w_3, \dots, w_{s_1}\) are the leaves of \(K_{1,n_1}\). We have the following two possibilities to obtain the stars \(K_{1,n_2}\) and \(K_{1,n_3}\):
1. If \(n_2 \le t - s_1\), then \(w_{s_1+1}, w_{s_1+2}, ..., w_{s_1+n_2}\) are the leaves of \(K_{1,n_2}\). Since \(n_3 \le n_2 \le t - s_1 \le t - 1\), we have \(u_2, u_3, ..., u_{n_3+1}\) are the leaves of \(K_{1,n_3}\), see Figure 6.
Figure 6 A disjoint union of stars \(\bigcup_{i=1}^{3} K_{1,n_i}\) in \(G_R\), if p < t.
2. If \(t-s_1 \le n_2 \le n_1\) and let \(s_2 = n_2 - (t-s_1) \ge 1\), then \(w_{s_1+1}, w_{s_1+2}, \ldots, w_t, u_2, u_3, \ldots, u_{s_2+1}\) are the leaves of \(K_{1,n_2}\). Since \(n_1 + n_2 = 2t - 2 + s_2\), so \(n_3 \le t - s_2 - 1\). Then, \(u_{s_2+2}, u_{s_2+3}, \ldots, u_{n_3+s_2+1}\) are the leaves of \(K_{1,n_3}\).
Therefore, we have a disjoint union of stars \(\bigcup_{i=1}^{3} K_{1,n_i}\) in \(G_R\), where \(u_1, v_1\) and \(v_{p+1}\) are their centers.
Theorem 3.3 Let \[n_1 \ge n_2 \ge n_3 \ge n_4 \ge 1\] be positive integers. Let \(A = \left[\frac{4+n_1+n_2+n_3+n_4}{3}\right]\) and \(B = \left[\frac{n_1+3}{2}\right]\). Then, \(m_3\left(\bigcup_{i=1}^4 K_{1,n_i}, P_3\right) = \max\{A, B\}\).
Proof. Let \(t = \max\{A, B\}\). To show that \(m_3(\bigcup_{i=1}^4 K_{1,n_i}, P_3) \ge t\), we consider the following two possibilities for the value of t:
- 1. If \(A \ge B\), then \(t = \left\lceil \frac{4+n_1+n_2+n_3+n_4}{3} \right\rceil\). We make the edges of graph \(K_{3\times(t-1)}\) red. Since \(\left| V\left(K_{3\times(t-1)}\right) \right| = 3t 3 = 3 \left\lceil \frac{4+n_1+n_2+n_3+n_4}{3} \right\rceil 3 < 4 + n_1 + n_2 + n_3 + n_4 = \left| V\left(\bigcup_{i=1}^4 K_{1,n_i}\right) \right|\), \(V\left(K_{3\times(t-1)}\right)\) contains neither a blue \(P_3\) nor the red \(\bigcup_{i=1}^4 K_{1,n_i}\).
- 2. If A < B, then \(t = \left\lceil \frac{n_1 + 3}{2} \right\rceil\). Suppose that \(m_3 \left( \bigcup_{i=1}^4 K_{1,n_i}, P_3 \right) < t\). Then, \(n_1 \le 2(t-1) 3 = 2 \left\lceil \frac{n_1 + 3}{2} \right\rceil 5 < n_1\), which is a contradiction.
Therefore, \(m_3(\bigcup_{i=1}^4 K_{1,n_i}, P_3) \ge t\).
Now, we show that \(m_3(\bigcup_{i=1}^4 K_{1,n_i}, P_3) \le t\). We consider any coloring of \(K_{3\times t} = G_R \oplus G_B\) such that \(G_B\) does not contain a blue \(P_3\), so \(\Delta(G_B) \le 1\). Then, \(G_B\) is a matching graph, see Figures 4 and 5. The centers of stars \(K_{1,n_1}, K_{1,n_2}, K_{1,n_3}\) and \(K_{1,n_4}\) are \(u_1, v_1, v_{p+1}\) and \(w_1\), respectively. We have the following two possibilities to obtain \(K_{1,n_4}\) and \(K_{1,n_2}\):
- 1. If \(n_1 \le t-2\), then \(v_2, v_3, \dots, v_p, v_{p+2}, \dots, v_{p+q+1}, \dots, v_{n_1+2}\) are the leaves of \(K_{1,n_1}\). Since \(n_2 \le n_1 \le t-2\), we have \(w_2, \dots, w_{n_2+1}\) are the leaves of \(K_{1,n_2}\). There are \(t-n_2+1 \ge 1\) vertices in \(W-\{w_1,w_2,\dots,w_{n_2+1}\}\). We have the following two possibilities to obtain \(K_{1,n_3}\) and \(K_{1,n_4}\):
- a) If \(n_3 \le t (n_2 + 1)\), then \(w_{n_2+2}, w_{n_2+3}, ..., w_{n_2+n_3+1}\) and \(u_2, u_3, ..., u_{n_4+1}\) are the leaves of \(K_{1,n_3}\) and \(K_{1,n_4}\), respectively.
- b) If \(t-(n_2+1) < n_3 \le n_2\), let \(s_1=n_3-(t-(n_2+1)) \ge 1\), then \(w_{n_2+2}, w_{n_2+3}, \ldots, w_t, u_2, u_3, \ldots, u_{s_1+1}\) are the leaves of \(K_{1,n_3}\). Since \(n_1+n_2+n_3 \le 2t-3-s_1, n_4 \le t-s_1-1\). Then, \(u_{s_1+2}, u_{s_1+3}, \ldots, u_{s_1+n_4+1}\) are the leaves of \(K_{1,n_4}\).
- 2. If \(t-1 \le n_1 \le 2t-3\) and let \(s_2 = n_1 (t-2) \ge 1\), then \(v_2, v_3, ..., v_p, v_{p+2}, ..., v_{p+q}, v_{p+q+1}, ..., v_t, w_2, w_3, w_{s_2+1}\) are the leaves of \(K_{1,n_1}\). We have three possibilities:
- a. If \(n_2 < t (s_2 + 1)\) and let \(s_3 = n_3 + n_2 + s_2 + 1 t \ge 1\), then \(w_{s_2+2}, w_{s_2+3}, \dots, w_{s_2+n_2+1}\) are the leaves of \(K_{1,n_2}\) and we have two possibilities:
- i. If \(n_3 \le t (n_2 + s_2 + 1)\), then \(w_{s_2 + n_2 + 2}, w_{s_2 + n_2 + 3}, ..., w_{s_2 + n_2 + n_3 + 1}\) are the leaves of \(K_{1,n_3}\). Since \(n_4 \le n_3\), so \(u_2, u_3, ..., u_{n_4 + 1}\) are the leaves of \(K_{1,n_4}\).
- ii. If \(t (n_2 + s_2 + 1) < n_3 \le n_2\), then \(w_{s_2 + n_2 + 2}, w_{s_2 + n_2 + 3}, \dots, w_t, u_2\), \(u_3, \dots, u_{s_3 + 1}\) are the leaves of \(K_{1,n_2}\). Since \(n_1 + n_2 + n_3 \le 2t 3 + 1\)
- a. If \(n_2 < t (s_2 + 1)\) and let \(s_3 = n_3 + n_2 + s_2 + 1 t \ge 1\), then \(w_{s_2+2}, w_{s_2+3}, \dots, w_{s_2+n_2+1}\) are the leaves of \(K_{1,n_2}\) and we have two possibilities:
\(s_3\), so \(n_4 \le t - 1 - s_3\). Then, \(u_{s_3+2}, u_{s_3+3}, \dots, u_{s_3+n_4+1}\) are the leaves of \(K_{1,n_4}\).
- b. If \(n_2=t-(s_2+1)\), then \(w_{s_2+2}, w_{s_2+3}, ..., w_t\) are the leaves of \(K_{1,n_2}\). Since \(n_1+n_2=2t-3+s_4\), so \(n_3+n_4\leq t-1-s_4\). Then, \(u_2,u_3,...,\ u_{n_3+1}\) and \(u_{n_3+2},u_{n_3+3},...,u_{n_3+n_4+1}\) are the leaves of \(K_{1,n_3}\) and \(K_{1,n_4}\), respectively.
- c. If \(t-(s_2+1) < n_2 \le n_1\) and let \(s_4=n_2+s_2+1-t \le 1\), then \(w_{s_2+2}, w_{s_2+3}, ..., w_t, u_2, u_3, ..., u_{s_4+1}\) are the leaves of \(K_{1,n_2}\). Since \(n_1+n_2=2t-3+s_4\), so \(n_3+n_4 \le t-1-s_4\). Then, \(u_{s_4+2}, u_{s_4+3}, ..., u_{s_4+n_3+1}\) and \(u_{s_4+n_3+2}, u_{s_4+n_3+3}, ..., u_{s_4+n_3+n_4+1}\) are the leaves of \(K_{1,n_3}\) and \(K_{1,n_4}\), respectively.
Therefore, we find a disjoint union of stars \(\bigcup_{i=1}^{4} K_{1,n_i}\) in \(G_R\), where \(u_1, v_1, v_{p+1}\) and \(w_1\) are their centers.
From Theorems 3.1, 3.2 and 3.3 we obtain that \(m_3(\bigcup_{i=1}^k K_{1,n_i}, P_3) = \max\{A, B\}\), where \(A = \left\lceil \frac{k+n_1+n_2+\cdots+n_k}{3} \right\rceil\) and \(B = \left\lceil \frac{n_1+k-1}{2} \right\rceil\), for k=2,3,4. For \(k \geq 5\), it seems that the tripartite Ramsey number of \(\bigcup_{i=1}^k K_{1,n_i}\) and \(P_3\) is also \(\max\{A, B\}\). For example, \(m_3(2K_{1,6} \cup 2K_{1,5} \cup K_{1,4} \cup K_{1,3} \cup K_{1,2}, P_3) = \max\left\{ \left\lceil \frac{7+6+6+5+5+4+3+2}{3} \right\rceil, \left\lceil \frac{6+6}{2} \right\rceil \right\} = 13\) and \(m_3(K_{1,100} \cup K_{1,55} \cup 8K_{1,1}, P_3) = \max\left\{ \left\lceil \frac{10+100+55+1+1+1+1+1+1+1+1}{3} \right\rceil, \left\lceil \frac{100+9}{2} \right\rceil \right\} = 58\), which can be seen in Figures 7 and 8, respectively.
Figure 7 A disjoint union of stars \(2K_{1,6} \cup 2K_{1,5} \cup K_{1,4} \cup K_{1,3} \cup K_{1,2}\) in \(K_{3\times 13}\).
Figure 8 A disjoint union of stars \(K_{1,100} \cup K_{1,55} \cup 8K_{1,1}\) in \(K_{3\times58}\).
Note that from these figures, we may have a different way to choose the stars than as mentioned in the proof of Theorem 3.3. Moreover, to obtain \(m_3(2K_{1,6} \cup 2K_{1,5} \cup K_{1,4} \cup K_{1,3} \cup K_{1,2}, P_3)\) and \(m_3(K_{1,100} \cup K_{1,55} \cup 8K_{1,1}, P_3)\) we cannot use the technique for choosing stars in the proof of Theorem 3.3. So, we would need to develop a new technique to prove the following conjecture.
Conjecture 3.1 Let \[n_1 \ge n_2 \ge \cdots \ge n_k \ge 1\] be positive integers. Let \(A = \left\lceil \frac{k+n_1+n_2+\cdots+n_k}{3} \right\rceil\) and \(B = \left\lceil \frac{n_1+k-1}{2} \right\rceil\). Then, \(m_3 \left( \bigcup_{i=1}^k K_{1,n_i}, P_3 \right) = \max\{A, B\}\).
Acknowledgement
This research has been supported by research grant Program Penelitian, Pengabdian Kepada Masyarakat dan Inovasi (P3MI) ITB and Penelitian Dasar Unggulan Perguruan Tinggi, Ministry of Research, Technology and Higher Education, Indonesia.