For a graph \(F\) and a positive integer \(t\), the edge-disjoint Ramsey number \(ER_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 edge-disjoint monochromatic copies of a subgraph isomorphic to \(F\). Since \(ER_1(F)\) is in fact the Ramsey number of \(F\), this concept extends the standard concept of Ramsey number. We investigate the edge-disjoint Ramsey numbers \(ER_t(K_{1, n})\) of the stars \(K_{1, n}\) of size \(n\). Formulas are established for \(ER_t(K_{1, n})\) for all positive integers \(n\) and \(t = 2, 3, 4\) and bounds are presented for \(ER_t(K_{1, n})\) for all positive integers \(n\) and \(t \ge 5\). Furthermore, exact values of \(ER_t(K_{1, n})\) are determined for \(n = 3, 4\) and several integers \(t \ge 5\).
Perhaps the best known Ramsey number is \(R(K_3, K_3)\), sometimes written as \(R(K_3)\). This is the minimum positive integer \(n\) such that for every red-blue coloring of the complete graph \(K_n\) of order \(n\), there is always a monochromatic subgraph \(F\) of \(K_n\) where \(F\) is isomorphic to \(K_3\). It is well known that \(R(K_3) = 6\). This result was established by Greenwood and Gleason [4] in 1955. In fact, this result essentially appeared as Problem A2 in the 1953 William Lowell Putnam Exam (see [4]).
While every red-blue coloring of \(K_6\) always results in a monochromatic triangle \(K_3\) (all whose edges are colored the same), it turns out that every red-blue coloring of \(K_6\) always results in at least two monochromatic triangles. 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. [2] Every red-blue coloring of \(K_7\) results in two edge-disjoint monochromatic triangles.
This brings up the problem of determining for a positive integer \(t\) and a graph \(F\) without isolated vertices, the minimum positive integer \(n\) such that for every red-blue coloring of the complete graph \(K_n\), there always exist \(t\) pairwise edge-disjoint monochromatic copies of the graph \(F\). Such an integer \(n\) is referred to as the edge-disjoint Ramsey number \(ER_t(F)\) of \(F\) in [2]. If \(t = 1\), then \(ER_1(F)=R(F)\) is the standard Ramsey number. Therefore, the concept of edge-disjoint Ramsey number extends the standard concept of Ramsey number. It is well-known that Ramsey numbers exist for every graph \(F\) (see [6]). This is also the case for edge-disjoint Ramsey numbers.
Observation 1.2. [2] For every graph \(F\) without isolated vertices and every positive integer \(t\), the number \(ER_t(F)\) exists and \(ER_t(F) \le ER_{t+1}(F)\).
By Proposition 1.1, \(ER_2(K_3)= 7\). We turn our intention here to investigating the edge-disjoint Ramsey numbers \(ER_t(F)\) where \(F= K_{1, n}\) is a star of order \(n+1\) and size \(n\). We refer to the book [] for notation and terminology not defined here. In [2] the following result was obtained for \(K_{1, 2}\).
Theorem 1.3. [2] For every positive integer \(t\), \[ER_t(K_{1, 2})= \lceil 2 \sqrt{t} + 1 \rceil.\]
We now investigate the numbers \(ER_t(K_{1,n})\) for certain values of \(n \ge 3\) and positive integers \(t\). First, we state the Ramsey numbers of stars, obtained by Burr and Roberts [1].
Theorem 1.4. [1] For \(n \ge 3\), \(R(K_{1, n}) =\left\{\begin{array}{ll} 2n & \mbox{ if $n$ is odd},\\ 2n-1 & \mbox{ if $n$ is even.} \end{array} \right.\)
Proposition 1.5. For integers \(n \ge 2\) and \(t \ge 2\),
\[ER_t(K_{1, n}) \le ER_{t+1}(K_{1, n})\le ER_t(K_{1, n})+1.\]
Proof. The lower bound is a consequence of Observation 1.2. To verify the upper bound, let \(N= ER_t(K_{1, n})+1\) and let there be given a red-blue coloring of \(G= K_N\). Next, let \(v \in V(G)\). Then \(G-v \cong K_{N-1}\). Since \(ER_t(K_{1, n})= N-1\), there are \(t\) pairwise edge-disjoint monochromatic copies \(F_1, F_2, \ldots, F_t\) of \(K_{1, n}\). By Observation 1.2 and Theorem 1.4, \(ER_t(K_{1, n}) = N-1\ge R(K_{1, n}) \ge 2n-1\) and so \(\deg_G v = N-1 \ge 2n-1\). Hence, there are at least \(n\) edges incident with \(v\) that have the same color, producing a monochromatic copy \(F_{t+1}\) of \(K_{1, n}\) that is edge-disjoint from \(F_i\) for \(1 \le i \le t\). Therefore, \(G\) contains \(t+1\) pairwise edge-disjoint monochromatic copies of \(K_{1, n}\) and so \[ER_{t+1}(K_{1, n})\le N = ER_t(K_{1, n})+1.\] ◻
In [5] the following results were obtained.
Proposition 2.1. [5]\(ER_2(K_{1, 3})=6\) and \(ER_3(K_{1, 3})=ER_4(K_{1, 3})= 7\).
We now determine \(ER_t(K_{1, 3})\) for \(5 \le t \le 7\). First, the following bound for \(ER_t(K_{1, n})\) when \(t \ge 2\) will be useful.
Proposition 2.2. For each integer \(t \ge 2\) \(ER_t(K_{1, 3})\ge \left\lceil \dfrac{3+\sqrt{9+24t}}{2} \right\rceil.\)
Proof. Let \(ER_t(K_{1, 3}) =k\). Then \(k \ge R(K_{1, 3}) = 6\) by Theorem 1.4. Hence, every red-blue coloring of \(G = K_k\) results in \(t\) pairwise edge-disjoint monochromatic copies of \(K_{1, 3}\). Consider a red-blue coloring of \(G\) such that the red subgraph is \(G_r=C_{k}\) and the blue subgraph is \(G_b=G-E(C_{k})\). Since \(G_r = C_k\) is 2-regular of order \(k \ge 6\), there is no red \(K_{1, 3}\) in \(G\). Thus, \(G_b\) contains \(t\) pairwise edge-disjoint copies of \(K_{1, 3}\). Since the size of \(G_b\) is \({k \choose 2}-k\), it follows that \({k \choose 2}-k \ge 3t\) or \(k^2 -3k-6t\ge 0\). Hence, \(k \ge \dfrac{3+\sqrt{9+24t}}{2}\) and so \(ER_t(K_{1, 3}) = k\ge \left\lceil \dfrac{3+\sqrt{9+24t}}{2} \right\rceil.\) ◻
Proposition 2.3. \(ER_5(K_{1, 3}) = 8\).
Proof. Since \(ER_5(K_{1, 3}) \le ER_4(K_{1, 3})+1= 8\) by Proposition 1.5 and \[ER_5(K_{1, 3}) \ge \left\lceil \dfrac{3+\sqrt{9+24\cdot 5}}{2} \right\rceil = 8,\] by Proposition 2.2, it follows that \(ER_5(K_{1, 3}) = 8\). ◻
In order to show \(ER_6(K_{1, 3})= 8\), we first introduce some additional definitions and notation as well as four lemmas. We omit the proofs of these lemmas since they are straightforward. For a graph \(G\), let \(v_1, v_2, \ldots, v_k\) be \(k\) vertices of \(G\) such that \(\deg v_i = d_i\) for \(1 \le i \le k\) and \(d_1 \le d_2 \le \cdots \le d_k\). Let \(S=(s_1,s_2, \ldots, s_k)\) be a sequence of \(k\) positive integers. We say that the degree sequence of \(v_1, v_2, \ldots, v_k\) is at least \(S\) if \(d_i\ge s_i\) for \(1 \le i \le k\). For an integer \(n \ge 2\), we write \((a^n)\) for a sequence \((a, a, \ldots, a)\) of \(n\) elements \(a\).
Lemma 2.4 Let \(H\) be a graph of order \(8\). If
(1) \(\Delta(H) \ge 6\),
(2) \(H\) contains two vertices \(x\) and \(y\) such that \(\deg x \ge 3\) and \(\deg y \ge 4\), or
(3) \(H\) contains five
vertices of degree \(3\) or more,
then \(H\) contains two pairwise
edge-disjoint copies of \(K_{1,
3}\).
Lemma 2.5 ] Let \(H\) be a graph of order \(8\). If \(H\) contains
(1) two vertices whose degree sequence is at least \((4, 6)\),
(2) three vertices whose degree sequence is at least \((3, 4, 5)\),
(3) five vertices whose degree sequence is at least \((3, 4^4)\),
(4) five vertices whose degree sequence is at least \((3^4, 6)\), or
(5) six vertices whose degree sequence is at least \((3^3, 4^3)\),
then \(H\) contains three pairwise
edge-disjoint copies of \(K_{1,
3}\).
Lemma 2.6 ] Let \(H\) be a graph of order \(8\). If \(H\) contains
(1) four vertices whose degree sequence is at least \((3, 4, 5, 6)\),
(2) five vertices whose degree sequence is at least \((3, 5^4)\),
(3) six vertices whose degree sequence is at least \((3^4, 5, 6)\),
(4) six vertices whose degree sequence is at least \((3^2, 4, 5^3)\),
(5) six vertices whose degree sequence is at least \((3, 4^4, 6)\),
(6) six vertices whose degree sequence is at least \((3^2, 4^3, 7)\), or
(7) seven vertices whose degree sequence is at least \((3, 4^5, 5)\),
then \(H\) contains four pairwise
edge-disjoint copies of \(K_{1,
3}\).
Lemma 2.7 ] Let \(H\) be a graph of order \(8\). If \(H\) contains
\((1)\) seven vertices whose degree sequence is at least \((5^7)\) or
\((2)\) eight vertices whose degree
sequence is at least \((4^4,
5^4)\),
then \(H\) contains five pairwise
edge-disjoint copies of \(K_{1,
3}\).
With the aid of Lemmas 2.4–2.7, we are able to determine the value of \(ER_6(K_{1, 3})\).
Theorem 2.8. \(ER_6(K_{1, 3}) = 8\).
Since the proof of Theorem 2.8 is quite lengthy, we will only provide an outline of a proof. Since \(ER_6(K_{1, 3}) \ge ER_5(K_{1, 3}) = 8\) by Proposition 2.3, it remains to show that \(ER_6(K_{1, 3}) \le 8\). To establish this inequality, it is required to show that for every red-blue coloring of \(G = K_8\), there are six pairwise edge-disjoint monochromatic copies of subgraphs of \(K_8\) that are isomorphic to \(K_{1, 3}\). So, let there be given a red-blue coloring of \(G\) resulting in the red subgraph \(G_r\) of order 8 and size \(m_r\) and the blue subgraph \(G_b\) of order 8 and size \(m_b\). We may assume that \(m_r \ge m_b\). Since the size of \(G\) is \({8\choose 2} = 28\), it follows that \(m_r \ge 14\). By investigating the possible values of \(\delta(G_r)\) and \(\Delta_r(G_r)\) as well as the possible degree sequences of \(G_r\), we show that every red-blue coloring of \(G\) produces six pairwise edge-disjoint monochromatic copies of subgraphs of \(K_8\) that are isomorphic to \(K_{1, 3}\).
We begin by investigating the situation where \(\delta(G_r) \ge 5\). Here, we show that the red subgraph \(G_r\) has six pairwise edge-disjoint copies of \(K_{1, 3}\) by considering three cases, according to whether \(\Delta(G_r)\) is \(5, 6,\) or \(7\). If \(\Delta(G_r)=5\), then \(G_r\) is a 5-regular graph of order \(8\). Since the complement \(\overline{G_{r}}\) of \(G_{r}\) is one of \(C_8\), \(2C_4\) (the union of two vertex-disjoint copies of a 4-cycle \(C_4\)), or \(C_3 + C_5\) (the union of the vertex-disjoint cycles \(C_3\) and \(C_5\)), there are exactly three possibilities for \(G_{r}\), namely \(\overline{C_8}\), \(\overline{2C_4}\), or \(\overline{C_3 + C_5}\). In each of these three 5-regular graphs of order 8, there are six pairwise edge-disjoint copies \(F_1, F_2, \ldots, F_6\) of \(K_{1, 3}\). This is shown in Figure 2 where an edge labeled \(i\) belongs to \(F_i\) for \(1 \le i \le 6\). Observe that the size of \(G_{r}\) is 20 and \(\sum_{i=1}^6 |E(F_i)|= 18\) and so two edges of \(G_{r}\) do not belong to any \(F_i\) for \(1 \le i \le 6\).
If \(\Delta(G_r)=6\) or \(\Delta(G_r)=7\), then there are three possible cases, according to the degree sequences of \(G_r\). Applying Lemmas 2.4–2.7 to the red subgraph \(G_r\), we are able to show that \(G_r\) contains six pairwise edge-disjoint copies of \(K_{1, 3}\) in each of these cases.
For the situation where \(\delta(G_r)\le 4\), it follows that \(\Delta(G_b) \ge 3\) and so the blue subgraph \(G_b\) contains at least one copy of \(K_{1, 3}\). Here, eight cases are considered according to the degrees of the vertices of \(G_r\). In each case, we show that for a desired number \(x\) of pairwise edge-disjoint copies of \(K_{1, 3}\) in \(G_r\) where \(3 \le x \le 5\), there are \(x-2\) pairwise edge-disjoint copies \(F_1, F_2, \ldots, F_{x-2}\) of \(K_{1, 3}\) in \(G_r\) such that there are two vertices \(u_1\) and \(u_2\) in the subgraph \(G_r' =G_r-[E(F_1)\cup E(F_2) \cup \cdots \cup E(F_{x-2})]\) for which \(\deg_{G_r'} u_1 \ge 3\) and \(\deg_{G_r'} u_2 \ge 4\). Consequently, by Lemma 2.4 there are two edge-disjoint copies \(F_{x-1}\) and \(F_{x}\) of \(K_{1, 3}\) in \(G_r'\) such that \(F_{x-1}\) is centered at \(u_1\) and \(F_{x}\) is centered at \(u_2\). This then implies that \(G_r\) has \(x\) pairwise edge-disjoint copies of \(K_{1, 3}\). Furthermore, we show that the blue subgraph \(G_b\) has at least \(6-x\) pairwise edge-disjoint copies of \(K_{1, 3}\). Consequently, there are six pairwise edge-disjoint monochromatic copies of \(K_{1, 3}\) in \(G\).
Therefore, Theorem 2.8 can be verified using an extensive case-by-case analysis together with Lemmas 2.4–2.7. Knowing that \(ER_6(K_{1, 3}) = 8\) makes it easy to determine \(ER_7(K_{1, 3})\). First, \(ER_7(K_{1, 3})\le ER_6(K_{1, 3}) +1= 9\) by Proposition 1.5 and Theorem 2.8. Next, \(ER_7(K_{1, 3}) \ge 9\) by Proposition 2.2. Therefore, we have the following result.
Proposition 2.9. \(ER_7(K_{1, 3})= 9.\)
We mentioned that \(ER_t(K_{1,3})\) was determined in [5] for \(1 \le t \le 4\). Actually, for \(1 \le t \le 4\), \(ER_t(K_{1,n})\) can be determined for every integer \(n \ge 2\).
Theorem 3.1. For each integer \(n \ge 2\), \(ER_2(K_{1, n})= 2n\).
Proof. We saw that \(ER_2(K_{1, 2})= 4\) and \(ER_2(K_{1, 3})= 6\). Thus, we may assume that \(n \ge 4\). We consider two cases, according to whether \(n\) is even or \(n\) is odd.
Case 1\(1\). \(n \ge 4\) is even. In this case, \(R(K_{1, n})= 2n-1\). First, we show that \(ER_2(K_{1, n}) \le 2n\). Let there be given a red-blue coloring of \(G= K_{2n}\). Since \(R(K_{1, n}) =2n-1\), it follows that \(G\) contains a monochromatic copy \(F_1\) of \(K_{1, n}\). Let \(v \in V(G)-V(F_1)\). Since \(\deg_G v = 2n-1\), there are at least \(n\) edges incident with \(v\) that have the same color, producing a monochromatic copy \(F_2\) of \(K_{1, n}\) that is edge-disjoint from \(F_1\). Therefore, \(ER_2(K_{1, n})\le 2n\).
Next, we show that \(ER_2(K_{1, n})\ge 2n\). Let there be given a red-blue coloring of \(H= K_{2n-1}\) such that the blue subgraph \(G_b\) is obtained from \(H_1= K_n\) with \(V(K_n)=\{u_1, u_2, \ldots, u_n\}\) and \(H_2= K_{n-1}\) with \(V(K_{n-1})=\{v_1, v_2, \ldots, v_{n-1}\}\) by adding the edges \(u_iv_i\) for \(1 \le i \le n-1\). Thus, \(\deg_{G_b} u_i = n\) for \(1 \le i \le n-1\) and all other vertices of \(G_b\) have degree \(n-1\). Hence, \(G_b\) contains a copy \(F_i\) of \(K_{1, n}\) whose center is \(u_i\) where \(1 \le i \le n-1\). For each pair \(i, j \in \{1, 2, \ldots, n-1\}\) and \(i \ne j\), both \(F_i\) and \(F_j\) contain the edge \(u_iu_j\) and so are not edge-disjoint. Furthermore, \(\deg_{G_b} u_n=\deg_{G_b}v_i = n-1\) for \(1 \le i \le n-1\). Thus, there is no \(K_{1, n}\) centered at \(u_n\) or at \(v_i\) for \(1 \le i \le n-1\). Hence, \(G_b\) does not contain two edge-disjoint copies of \(K_{1, n}\). Every vertex of the red subgraph \(G_r\) has degree \(n-2\) or \(n-1\). Thus, there is no \(K_{1, n}\) in \(G_r\). Therefore, this red-blue coloring does not produce two edge-disjoint monochromatic copies of \(K_{1, n}\) and so \(ER_2(K_{1, n}) \ge 2n\). Hence, \(ER_2(K_{1, n}) = 2n\) when \(n \ge 4\) is even.
Case 2\(2\). \(n \ge 5\) is odd. In this case, \(R(K_{1, n})= 2n\). Since \(ER_2(K_{1, n}) \ge R(K_{1, n})= 2n\), it remains to show that \(ER_2(K_{1, n}) \le 2n\). Let there be given a red-blue coloring of \(H= K_{2n}\) resulting in a red subgraph \(H_r\) and blue subgraph \(H_b\). If \(\Delta(H_r) \ge n\) and \(\Delta(H_b) \ge n\), then \(H\) contains two edge-disjoint monochromatic copies of \(K_{1, n}\). Thus, we may assume that \(\Delta(H_r) \le n-1\) and so \(\delta(H_b) \ge n\). If \(H_b = K_{2n}\), then for every two vertices \(u\) and \(v\), there are two edge-disjoint copies of \(K_{1, n}\) centered at \(u\) and \(v\). If \(H_b \ne K_{2n}\), then let \(x\) and \(y\) be two nonadjacent vertices of \(H_b\). Since \(\deg_{H_b} x \ge n\) and \(\deg_{H_b} y \ge n\), it follows that \(H_b\) contains two edge-disjoint copies of \(K_{1, n}\) centered at \(x\) and \(y\). Therefore, \(ER_2(K_{1, n})\le 2n\) and so \(ER_2(K_{1, n}) = 2n\) when \(n \ge 5\) is even. ◻
Theorem 3.2. For each integer \(n \ge 2\), \(ER_3(K_{1, n})=2n+1\).
Proof. By Theorem 3.1 and Proposition 1.5, it follows that \(ER_3(K_{1, n})\le 2n+1\). Thus, it remains to show that \(ER_3(K_{1, n})\ge 2n+1\). Define a red-blue coloring of \(G=K_{2n}\) with the red subgraph \(G_r = K_n \ \Box \ K_2\). Then \(G_r\) is an \(n\)-regular graph. Thus, two copies of \(K_{1, n}\) in \(G_r\) are edge-disjoint if and only if their centers are not adjacent. Since the vertex independent number of \(G_r\) is \(\alpha(G_r)= 2\), there are two edge-disjoint copies of \(K_{1, n}\) in \(G_r\) but no three pairwise edge-disjoint copies of \(K_{1, n}\) in \(G_r\). Furthermore, the blue subgraph \(G_b\) is an \((n-1)\)-regular graph and so there is no \(K_{1, n}\) in \(G_b\). Therefore, this red-blue coloring does not produce three pairwise edge-disjoint copies of \(K_{1, n}\) and so \(ER_3(K_{1, n})\ge 2n+1\). ◻
Next, we show that \(ER_4(K_{1, n})= ER_3(K_{1, n})= 2n+1\) for each integer \(n \ge 2\). Since \(ER_4(K_{1, 2})=5\) and \(ER_4(K_{1, 3}) = 7\) by Proposition 2.1, we may assume that \(n \ge 4\). Applying an extensive case-by-case analysis, the exact value of \(ER_4(K_{1, 4})\) can be determined, as we state next. Since this result is also a consequence of Proposition 1.5, Theorem 3.2, and a stronger result (Theorem 4.2) in Section 4, we omit its proof.
Theorem 3.3. \(ER_4(K_{1, 4})= 9\).
Theorem 3.3 can be extended to \(ER_4(K_{1, n})\) for all integers \(n \ge 2\).
Theorem 3.4. ] For each integer \(n \ge 2\), \(ER_4(K_{1, n})= 2n+1\).
Proof. Since \(ER_4(K_{1, 2})=5\) and \(ER_4(K_{1, 3}) = 7\) by Proposition 2.1 and \(ER_4(K_{1, 4}) = 9\) by Theorem 3.3, we may assume that \(n \ge 5\). By Observation 1.2, \(ER_4(K_{1, n}) \ge ER_3(K_{1, n})= 2n+1\). Hence, it remains to show that \(ER_4(K_{1, n})\le 2n+1\). Let there be given a red-blue coloring of \(G=K_{2n+1}\). Since \(ER_3(K_{1, n})=2n+1\), there are three pairwise edge-disjoint monochromatic copies \(F_1, F_2, F_3\) of \(K_{1, n}\). Let
\[H = G[E(F_1)\cup E(F_2) \cup E(F_3)].\]
Then \(|V(H)|= n_H \le 2n+1\) and \(|E(H)| = m_H = 3n\).
\(\star\) If \(n_H \le 2n\), then let \(v \in V(G)-V(H)\). Since \(\deg_G v= 2n\), there are at least \(n\) edges incident with \(v\) that have the same color and so there is a monochromatic copy \(F_4\) of \(K_{1, n}\) centered at \(v\) that is edge-disjoint from \(F_1, F_2, F_3\).
\(\star\) If there is an end-vertex \(u\) in \(H\), then \(u\) is incident with \(2n-1\) edges not in \(H\) and so there are at least \(n\) edges incident with \(u\) that have the same color. Thus, there is a monochromatic copy \(F_4\) of \(K_{1, n}\) centered at \(u\) that is edge-disjoint from \(F_1, F_2, F_3\).
\(\star\) Thus, we may assume that \(n_H = 2n+1\) and \(\delta(H) \ge 2\). Since at least three vertices have degree \(n\) in \(H\) (namely, the centers of \(F_1, F_2, F_3\)), it follows that \[\sum_{x \in V(H)} \deg_H x \ge 3n + 2(2n-2)= 7n-4.\]
Since \(n \ge 5\), it follows that \(3n = m_H \ge \dfrac{7n-4}{2} > 3n\), which is impossible. Therefore, \(ER_4(K_{1, n})= 2n+1\) when \(n \ge 5\). ◻
Since the numbers \(ER_t(K_{1, n})\) have been determined for all positive integers \(n\) and for every integer \(t\) with \(1 \le t \le 4\), it remains to investigate \(ER_t(K_{1, n})\) for positive integers \(n\) when \(t \ge 5\). In Proposition 2.3, we saw that \(ER_5(K_{1, 3})= 8\). We now determine \(ER_5(K_{1, 4})\). First, we state a useful lemma. Since the proof of this lemma is straightforward, we omit its proof.
Lemma 4.1 Let \(H\) be a graph of order \(9\). If \(H\) has
\((1)\) two vertices \(x\) and \(y\) such that \(\deg x \ge 4\) and \(\deg y \ge 5\) or
\((2)\) six vertices of degree \(4\),
then \(H\) contains two edge-disjoint
copies of \(K_{1, 4}\).
Theorem 4.2. \(ER_5(K_{1, 4})= 9\).
Proof. Since \(ER_3(K_{1, 4}) = 9\) by Theorem 3.2, it follows by Observation 1.2 that \(ER_5(K_{1, 4})\ge 9\). Thus, it remains to show that \(ER_5(K_{1, 4})\le 9\). Let there be given a red-blue coloring of \(G=K_{9}\) resulting in a red subgraph \(G_r\) of order 9 and size \(m_r\) and a blue subgraph \(G_b\) of order 9 and size \(m_b\). We may assume that \(m_r \ge m_b\). Since the size of \(G\) is \({9 \choose 2}= 36\), it follows that \(m_r \ge 18\). We consider ten cases depending on the number of vertices of degree 5 or more in \(G_r\).
Case \(1\). Every vertex of \(G_r\) has degree \(5\) or more. Thus, \(\Delta(G_b) \le 3\) and so \(G_b\) has no copy of \(K_{1, 4}\). We show that \(G_r\) has five pairwise edge-disjoint copies of \(K_{1, 4}\). Since \(6\le \Delta(G_r) \le 8\), there are three subcases, according to \(\Delta(G_r)=8\), \(\Delta(G_r)= 7\) or \(\Delta(G_r)= 6\).
Subcase \(1.1\). \(\Delta(G_r)= 8\). Then the degree sequence of \(G_r\) is at least \((5^8, 8)\). Let \(v_1\) be a vertex of minimum degree in \(G_r\). Then \(v_1\) is the center of a copy \(F_1\) of \(K_{1, 4}\). Let \(H_1= G_r-E(F_1)\). Then \(H_1\) contains eight vertices whose degree sequence is at least \((4^4, 5^3, 7)\). Let \(v_2\) be a vertex of minimum degree at least 4 in \(H_1\). Then \(v_2\) is the center of a copy \(F_2\) of \(K_{1, 4}\). Let \(H_2= H_1-E(F_2)\). Then \(H_2\) contains seven vertices whose degree sequence is at least
(i) \((3^3, 4, 5^2, 7)\),
(ii) \((3^2, 4^3, 5, 7)\),
(iii) \((3, 4^5, 7)\), or
(iv) \((4^6, 6)\).
Let \(v\) be a vertex in \(H_2\) such that \(\deg_{H_2} v \ge 7\), let \(v_3\) be a vertex of minimum degree at least 4 in \(H_2\) such that \(v_3\) is adjacent to \(v\), and let \(F_3\) be a copy of \(K_{1, 4}\) centered at \(v_3\) such that \(v\in V(F_3)\). Let \(H_3=H_2-E(F_3)\). Then \(H_3\) has two vertices \(x\) and \(y\) such that \(\deg_{H_3} x \ge 4\) and \(\deg_{H_3} y \ge 5\). By Lemma 4.1, \(H_3\) contains two edge-disjoint copies \(F_4\) and \(F_5\) of \(K_{1, 4}\) that are edge-disjoint from \(F_1, F_2\), and \(F_3\). Thus, \(G_r\) has five pairwise edge-disjoint copies of \(K_{1, 4}\).
Subcase \(1.2\). \(\Delta(G_r)= 7\). Then the degree sequence of \(G_r\) is at least \((5^8, 7)\). Let \(v_1\) be a vertex of minimum degree in \(G_r\) that is not adjacent to some vertex of degree 7. Then \(v_1\) is the center of a copy \(F_1\) of \(K_{1, 4}\). Let \(H_1= G_r-E(F_1)\). Then \(H_1\) contains eight vertices whose degree sequence is at least \((4^4, 5^3, 7)\). Proceeding as in Subcase 1.1, we see that \(G_r\) has five pairwise edge-disjoint copies \(F_1, F_2, F_3, F_4, F_5\) of \(K_{1, 4}\).
Subcase \(1.3\). \(\Delta(G_r)= 6\). Then the degree sequence of \(G_r\) is at least \((5^8, 6)\). Let \(v\) be a vertex of degree 6 in \(G_r\) and let \(v_1\) and \(v_2\) be the two vertices of \(G_r\) that are not adjacent to \(v\). Then \(v_1\) is the center of a copy \(F_1\) of \(K_{1, 4}\) such that \(v \notin V(F_2)\). Let \(H_1= G_r-E(F_1)\). Thus, \(H_1\) contains eight vertices whose degree sequence is at least \((4^4, 5^3, 6)\). Then \(v_2\) is the center of a copy \(F_2\) of \(K_{1, 4}\) in \(H_1\) such that \(v \notin V(F_2)\). Let \(H_2= G_r-E(F_2)\).
\(\star\) If \(\deg_{H_1} v_2=4\), then \(H_2\) contains seven vertices whose degree sequence is at least \((3^3, 4, 5^2, 6)\), \((3^2, 4^3, 5, 6)\), or \((3, 4^5, 6)\).
\(\star\) If \(\deg_{H_1} v_2\ge 5\), then we can choose \(F_2\) such that one vertex of degree at least 5 that is distinct from \(v\) does not belong to \(F_2\). Thus, \(H_2\) contains seven vertices whose degree sequence is at least \((3^4, 5^2, 6)\) or \((3^3, 4^2, 5, 6)\).
Let \(F_3\) be a copy of \(K_{1, 4}\) in \(H_2\) centered at a vertex of smallest degree at least 4 such that \(v \in V(F_3)\). Let \(H_3= H_2-E(F_3)\). Then there are two vertices \(x\) and \(y\) such that \(\deg_{H_3} x \ge 4\) and \(\deg_{H_3} y \ge 5\). By Lemma 4.1, \(H_3\) contains two edge-disjoint copies \(F_4\) and \(F_5\) of \(K_{1, 4}\) that are edge-disjoint from \(F_1, F_2\), and \(F_3\). Hence, \(G_r\) has five pairwise edge-disjoint copies of \(K_{1, 4}\).
Case \(2\). The number of vertices of degree \(5\) or more in \(G_r\) is \(8\). Since \(G_b\) contains a vertex of degree 4 or more, it follows that \(G_b\) has at least one copy of \(K_{1, 4}\). Thus, it remains to show that \(G_r\) contains four pairwise edge-disjoint copies of \(K_{1, 4}\). Here, \(G_r\) contains eight vertices whose degree sequence is at least \((5^8)\). Let \(F_1\) be a copy of \(K_{1, 4}\) of \(G_r\) centered at a vertex \(v\) of smallest degree that is at least 4 and let \(H_1=G_r-E(F_1)\). Thus, \(H_1\) contains seven vertices whose degree sequence is at least \((4^4, 5^3)\). Let \(F_2\) be a copy of \(K_{1, 4}\) centered at a vertex of smallest degree at least 4. Let \(H_2= H_1-E(F_1)\). Then either \(H_2\) contains two vertices \(x\) and \(y\) such that \(\deg_{H_2} x \ge 4\) and \(\deg_{H_2} y \ge 5\) or \(H_2\) contains six vertices of degree 4 or more. In either situation, it follows by Lemma 4.1 that \(H_2\) has two edge-disjoint copies \(F_3\) and \(F_4\) of \(K_{1, 4}\) that are edge-disjoint from \(F_1\). Since \(G_b\) has a copy of \(K_{1, 4}\), it follows that \(G\) has five pairwise edge-disjoint monochromatic copies of \(K_{1, 4}\).
Case \(3\). The number of vertices of degree \(5\) or more in \(G_r\) is \(7\). Thus, \(G_r\) has two vertices of degree at most 4. Hence, \(G_b\) has at least one copy of \(K_{1, 4}\).
\(\star\) First, suppose that \(G_r\) has two vertices of degree 4. Then the degree sequence of \(G_r\) is at least \((4^2, 5^7)\). Let \(F_1\) be a copy of \(K_{1, 4}\) in \(G_r\) centered at a vertex of smallest degree that is at least 4 that is not adjacent to some vertex of degree 5 or more. Let \(H_1=G_r-E(F_1)\). Thus, \(H_1\) contains eight vertices whose degree sequence is at least \((3, 4^3, 5^4)\). Let \(F_2\) be a copy of \(K_{1, 4}\) in \(G_r\) centered at a vertex of smallest degree that is at least 4 and let \(H_2= H_1-E(F_2)\). Then either \(H_2\) contains two vertices \(x\) and \(y\) such that \(\deg_{H_2} x \ge 4\) and \(\deg_{H_2} y \ge 5\) or \(H_2\) contains six vertices of degree 4 or more. In either situation, it follows by Lemma 4.1 that \(H_2\) has two edge-disjoint copies \(F_3\) and \(F_4\) of \(K_{1, 4}\) that are edge-disjoint from \(F_1\). Since \(G_b\) has a copy of \(K_{1, 4}\), it follows that \(G\) has five pairwise edge-disjoint monochromatic copies of \(K_{1, 4}\).
\(\star\) Next, suppose that \(G_r\) has at most one vertex of degree 4. Then \(G_b\) contains two vertices \(x\) and \(y\) such that \(\deg_{G_b} x \ge 4\) and \(\deg_{G_b} y \ge 5\) and so \(G_b\) contains two edge-disjoint copies of \(K_{1, 4}\) by Lemma 4.1. We show that \(G_r\) contains three pairwise edge-disjoint copies of \(K_{1, 3}\). Here, \(G_r\) has seven vertices whose degree sequence is at least \((5^7)\). Let \(F_1\) be a copy of \(K_{1, 4}\) of \(G_r\) centered at a vertex of smallest degree that is at least 4 and let \(H_1=G_r-E(F_1)\). Then \(H_1\) contains two vertices \(x\) and \(y\) such that \(\deg_{H_1} x \ge 4\) and \(\deg_{H_1} y \ge 5\). By Lemma 4.1, it follows that \(H_1\) has two edge-disjoint copies \(F_2\) and \(F_3\) of \(K_{1, 4}\) that are edge-disjoint from \(F_1\). Hence, \(G_r\) has three pairwise edge-disjoint copies of \(K_{1, 4}\). Since \(G_b\) has two copies of \(K_{1, 4}\), it follows that \(G\) has five pairwise edge-disjoint monochromatic copies of \(K_{1, 4}\).
Case \(4\). The number of vertices of degree \(5\) or more in \(G_r\) is \(6\). Thus, \(G_r\) has three vertices of degree at most 4 and \(G_b\) has at least three vertices of degree 4 or more. Hence, \(G_b\) has at least one copy of \(K_{1, 4}\). There are six vertices of \(G_r\) whose degree sequence is at least \((5^6)\). Let \(F_1\) be a copy of \(K_{1, 4}\) of \(G_r\) centered at a vertex of smallest degree that is at least 4 and let \(H_1=G_r-E(F_1)\). Thus, \(H_1\) contains two vertices \(x\) and \(y\) such that \(\deg_{H_1} x \ge 4\) and \(\deg_{H_1} y \ge 5\). Thus, \(H_1\) has two edge-disjoint copies of \(K_{1, 4}\) by Lemma 4.1. Hence, \(G_r\) contains three pairwise edge-disjoint copies of \(K_{1, 4}\). Thus, if \(G_b\) contains two edge-disjoint copies of \(K_{1, 4}\), then \(G\) has five pairwise edge-disjoint monochromatic copies of \(K_{1, 4}\).
Let \(T\) be the set of three vertices in \(G_r\) having degree less than 5 and let \(S\) be the set of six vertices in \(G_r\) having degree 5 or more. If one or more vertices of \(T\) have degree less than 4 in \(G_r\), then one or more vertices of \(T\) in \(G_b\) have degree 5 or more. This would result in \(G_b\) containing two edge-disjoint copies of \(K_{1, 4}\) by Lemma 4.1. Therefore, we may assume that every vertex of \(T\) has degree 4 in both \(G_r\) and \(G_b\). If two vertices of \(T\) are not adjacent in \(G_b\), then these two vertices are the centers of two edge-disjoint copies of \(K_{1, 4}\) in \(G_b\). Hence, we may assume that every two vertices of \(T\) are adjacent in \(G_b\). Therefore, \(G_r[T]=\overline{K}_3\). Since every vertex of \(T\) has degree 4 in \(G_r\), it follows that every vertex of \(T\) is adjacent to four vertices of \(S\). Each of the vertices of \(T\) is the center of a copy of \(K_{1, 4}\) in \(G_r\), resulting in three pairwise edge-disjoint copies of \(K_{1, 4}\). Furthermore, there are 12 edges joining the sets \(S\) and \(T\) in \(G_r\). Let \(H = G_r[S]\).
\(\star\) First, suppose that some vertex of \(S\), say \(v_1\), is adjacent to less than two vertices of \(T\) in \(G_r\). Then \(v_1\) is adjacent to at least four vertices in \(S\). Thus, \(v_1\) is the center of a copy \(F_1\) of \(K_{1, 4}\) in \(H\). Let \(F_2, F_3, F_4\) be the three pairwise edge-disjoint copies of \(K_{1, 4}\) centered at the vertices of \(T\) and let \(F_5\) be a copy of \(K_{1, 4}\) in \(G_b\). Therefore, \(G\) has five pairwise edge-disjoint monochromatic copies of \(K_{1, 4}\).
\(\star\) Next, suppose that no vertex of \(S\) is adjacent to less than two vertices of \(T\) in \(G_r\). Since there are 12 edges joining the sets \(S\) and \(T\) in \(G_r\), it follows that that every vertex of \(S\) is adjacent to exactly two of the three vertices of \(T\).
If some vertex of \(S\), say \(v_1\), has degree greater than 5 in \(G_r\), then \(v_1\) is the center of a copy \(F_1\) of \(K_{1, 4}\) in \(H\). Again, let \(F_2, F_3, F_4\) be the three pairwise edge-disjoint copies of \(K_{1, 4}\) centered at the vertices of \(T\) and let \(F_5\) be a copy of \(K_{1, 4}\) in \(G_b\). Therefore, \(G\) has five pairwise edge-disjoint monochromatic copies of \(K_{1, 4}\).
Thus, we may assume that no vertex of \(S\) has degree greater than 5 in \(G_r\). This implies that \(H = G_r[S]\) is a 3-regular graph of order 6. There are only two possibilities for \(H\), namely, \(K_{3, 3}\) and \(C_3 \ \Box \ K_2\). Since every vertex of \(S\) is adjacent to exactly two of the three vertices of \(T\), there are four pairwise edge-disjoint copies \(F_1, F_2, F_3, F_4\) of \(K_{1, 4}\) centered at four vertices of \(S\) in each situation. This is shown in Figure 3, where an edge labeled \(i\) belongs to \(F_i\) for \(i = 1, 2, 3, 4\) and each bold edge joins a vertex of \(S\) and a vertex of \(T\). Let \(F_5\) be a copy of \(K_{1, 4}\) in \(G_b\). Therefore, \(G\) has five pairwise edge-disjoint monochromatic copies of \(K_{1, 4}\).
Case \(5\). The number of vertices of degree \(5\) or more in \(G_r\) is \(5\). Again, \(G_b\) has at least one copy of \(K_{1, 4}\). Let \(T\) be the set of four vertices in \(G_r\) having degree less than 5 and let \(S\) be the set of five vertices in \(G_r\) having degree 5 or more. Since the number of odd vertices in \(G_r\) is even, either \(G_r\) has a vertex of degree 3 or less or \(G_r\) has a vertex degree 6 or more. We consider these two subcases.
Suncase \(5.1\). \(G_r\) has a vertex of degree \(3\) or less. Then \(G_b\) has two edge-disjoint copies \(F_4\) and \(F_5\) of \(K_{1, 4}\) by Lemma 4.1. We show that \(G_r\) has three pairwise edge-disjoint copies of \(K_{1, 4}\). Let \(u \in S\). Since \(\deg_{G_r}u \ge 5\), it follows that \(u\) is adjacent to a vertex \(v\in T\). Let \(F_1\) be a copy of \(K_{1, 4}\) centered at \(u\) such that \(uv \in E(F_1)\). Let \(H_1=G_r-E(F_1)\). Thus, \(H_1\) contains two vertices \(x\) and \(y\) such that \(\deg_{H_1} x \ge 4\) and \(\deg_{H_1} y \ge 5\). Thus, \(H_1\) has two edge-disjoint copies \(F_2\) and \(F_3\) of \(K_{1, 4}\) by Lemma 4.1. Hence, \(G_r\) contains three pairwise edge-disjoint copies of \(K_{1, 4}\). Therefore, \(G\) has five pairwise edge-disjoint monochromatic copies of \(K_{1, 4}\).
Subcase \(5.2\). \(G_r\) has a vertex of degree \(6\) or more. Then \(G_r\) has five vertices whose degree sequence is at least \((5^4, 6)\). Let \(F_1\) be a copy of \(K_{1, 4}\) centered at a vertex of smallest degree that is at least 4 and let \(H_1=G_r-E(F_1)\). Thus, \(H_1\) contains two vertices \(x\) and \(y\) such that \(\deg_{H_1} x \ge 4\) and \(\deg_{H_1} y \ge 5\) and so \(H_1\) has two edge-disjoint copies \(F_2\) and \(F_3\) of \(K_{1, 4}\) by Lemma 4.1. Hence, \(G_r\) contains three pairwise edge-disjoint copies of \(K_{1, 4}\). If \(G_r\) has a vertex of degree less than 4, then \(G_b\) has two edge-disjoint copies of \(K_{1, 4}\) by Lemma 4.1 and so \(G\) has five pairwise edge-disjoint monochromatic copies of \(K_{1, 4}\). Thus, we may assume that every vertex of \(T\) has degree 4 in \(G_r\) and in \(G_b\). If there are two vertices of \(T\) that are not adjacent in \(G_b\), then \(G_b\) has two edge-disjoint copies of \(K_{1, 4}\) centered at these two vertices. Thus, we may assume that \(G_b[T]= K_4\) and so \(G_r[T]= \overline{K}_4\). Therefore, there are four pairwise edge-disjoint copies of \(K_{1, 4}\) in \(G_r\) centered at the four vertices of \(T\). Since \(G_b\) has a copy of \(K_{1, 4}\), it follows that \(G\) has five pairwise edge-disjoint monochromatic copies of \(K_{1, 4}\).
Case \(6\). The number of vertices of degree \(5\) or more in \(G_r\) is \(4\). Let \(T\) be the set of five vertices in \(G_r\) having degree less than 5 and let \(S\) be the set of four vertices in \(G_r\) having degree 5 or more. Next, let \(u \in S\). Since \(\deg_{G_r}u \ge 5\), it follows that \(u\) is adjacent to a vertex \(v\in T\). Let \(F_1\) be a copy of \(K_{1, 4}\) centered at \(u\) such that \(uv \in E(F_1)\) and let \(H_1=G_r-E(F_1)\). Thus, \(H_1\) contains two vertices \(x\) and \(y\) such that \(\deg_{H_1} x \ge 4\) and \(\deg_{H_1} y \ge 5\). Thus, \(H_1\) has two edge-disjoint copies \(F_2\) and \(F_3\) of \(K_{1, 4}\) by Lemma 4.1. If \(G_b[T]= K_5\), then \(G_r[T]= \overline{K}_5\) and so there are five pairwise edge-disjoint copies of \(K_{1, 4}\) in \(G_r\) centered at the vertices of \(T\). Thus, we may assume that there are two vertices in \(T\) that are not adjacent in \(G_b\). Then \(G_b\) has two edge-disjoint copies \(F_4\) and \(F_5\) of \(K_{1, 4}\) centered at these two vertices. Therefore, \(G\) has five pairwise edge-disjoint monochromatic copies of \(K_{1, 4}\).
Case \(7\). The number of vertices of degree \(5\) or more in \(G_r\) is \(3\). Let \(u\) and \(v\) be two vertices of degree 5 or more in \(G_r\), let \(F_1\) be a copy of \(K_{1, 4}\) centered at \(u\) such that \(uv \notin E(F_1)\), and let \(H_1=G_r-E(F_1)\). Thus, \(H_1\) contains two vertices \(x\) and \(y\) such that \(\deg_{H_1} x \ge 4\) and \(\deg_{H_1} y \ge 5\). Hence, \(H_1\) has two edge-disjoint copies \(F_2\) and \(F_3\) of \(K_{1, 4}\) by Lemma 4.1. Since \(G_b\) has six vertices of degree 4, it follows by Lemma 4.1 that \(G_b\) has two edge-disjoint copies \(F_4\) and \(F_5\) of \(K_{1, 4}\). Therefore, \(G\) has five pairwise edge-disjoint monochromatic copies of \(K_{1, 4}\).
Case \(8\). The number of vertices of degree \(5\) or more in \(G_r\) is \(2\). By Lemma 4.1, both \(G_r\) and \(G_b\) have at least two edge-disjoint copies of \(K_{1, 4}\). We consider four subcases.
Subcase \(8.1\). \(G_r\) has at least two vertices of degree \(3\) or less. Then \(G_b\) has seven vertices whose degree sequence is at least \((4^5, 5^2)\). Let \(u, v \in V(G_b)\) such that \(\deg_{G_b} u \ge 5\) and \(\deg_{G_b} v \ge 5\). Then there is a copy \(F_1\) of \(K_{1, 4}\) in \(G_b\) centered at \(u\) such that \(uv \notin E(F_1)\). Let \(H_1=G_b-E(F_1)\). Then \(H_1\) contains two vertices \(x\) and \(y\) such that \(\deg_{H_1} x \ge 4\) and \(\deg_{H_1} y \ge 5\). Thus, \(H_1\) has two edge-disjoint copies \(F_2\) and \(F_3\) of \(K_{1, 4}\) by Lemma 4.1. Hence, \(G_b\) has three pairwise edge-disjoint copies of \(K_{1, 4}\). Since \(G_r\) has at least two edge-disjoint copies of \(K_{1, 4}\), it follows that \(G\) has five pairwise edge-disjoint monochromatic copies of \(K_{1, 4}\).
Subcase \(8.2\). \(G_r\) has a vertex of degree \(2\) or less. Then \(G_b\) has seven vertices whose degree sequence is at least \((4^6, 6)\). Let \(F_1\) be a copy of \(K_{1, 4}\) cantered at a vertex of smallest degree at least 4 and let \(H_1=G_b-E(F_1)\). Then \(H_1\) contains two vertices \(x\) and \(y\) such that \(\deg_{H_1} x \ge 4\) and \(\deg_{H_1} y \ge 5\). Thus, \(H_1\) has two edge-disjoint copies \(F_2\) and \(F_3\) of \(K_{1, 4}\) by Lemma 4.1. Hence, \(G_b\) has three pairwise edge-disjoint copies of \(K_{1, 4}\). Since \(G_r\) has at least two edge-disjoint copies of \(K_{1, 4}\), it follows that \(G\) has five pairwise edge-disjoint monochromatic copies of \(K_{1, 4}\).
Subcase \(8.3\). \(G_r\) has exactly one vertex of degree \(3\) and no other vertex of degree less than \(4\). Then \(G_b\) has seven vertices with degree sequence at least \((4^6, 5)\). Therefore, \(G_b\) has a vertex \(u\) of degree 4 that is not adjacent to the vertex \(v\) of degree 5 in \(G_b\). Let \(F_1\) be a copy of \(K_{1, 4}\) and let \(H_1= G_b-E(F_1)\). Then \(H_1\) contains two vertices \(x\) and \(y\) such that \(\deg_{H_1} x \ge 4\) and \(\deg_{H_1} y \ge 5\). Thus, \(H_1\) has two edge-disjoint copies \(F_2\) and \(F_3\) of \(K_{1, 4}\) by Lemma 4.1. Since \(G_r\) has at least two edge-disjoint copies of \(K_{1, 4}\), it follows that \(G\) has five pairwise edge-disjoint monochromatic copies of \(K_{1, 4}\).
Subcase \(8.4\). \(G_r\) has no vertex of degree \(3\) or less. Then the degree sequence of \(G_r\) is at least \((4^7, 5^2)\). Then \(G_r\) has three pairwise edge-disjoint copies of \(K_{1, 4}\) (by the argument for \(G_b\) in Subcase 8.3). Since \(G_b\) has at least two edge-disjoint copies of \(K_{1, 4}\), it follows that \(G\) has five pairwise edge-disjoint monochromatic copies of \(K_{1, 4}\).
Case \(9\). The number of vertices of degree \(5\) or more in \(G_r\) is \(1\). Again, both \(G_r\) and \(G_b\) have at least two edge-disjoint copies of \(K_{1, 4}\). If \(G_r\) has seven vertices with degree sequence at least \((4^6, 5)\), then \(G_r\) has three pairwise edge-disjoint copies of \(K_{1, 4}\) (by the argument for \(G_b\) in Subcase 8.3). If \(G_r\) does not have seven such vertices, then \(G_r\) has at most six vertices of degree 4 or more and so \(G_r\) has at least three vertices of degree 3 or less. Hence, \(G_b\) has eight vertices with degree sequence at least \((4^5, 5^3)\). Then \(G_b\) has three pairwise edge-disjoint copies of \(K_{1, 4}\) (by the argument for \(G_b\) in Subcase 8.1). In either situation, \(G\) has five pairwise edge-disjoint monochromatic copies of \(K_{1, 4}\).
Case \(10\). The number of vertices of degree \(5\) or more in \(G_r\) is \(0\). Since \(m_r \ge 18\), it follows that \(G_r\) is a 4-regular graph of order 9 and so \(G_b\) is also a 4-regular graph of order 9. By Lemma 4.1, both \(G_r\) and \(G_b\) contain two edge-disjoint copies of \(K_{1, 4}\). Let \(F_1\) be a copy of \(K_{1, 4}\) in \(G_b\) and let \(H_1 = G_b – E(F_1)\). Then \(H_1\) contains eight vertices whose degree sequence is \((3^4, 4^4)\). Let \(T\) be the set of four vertices of degree 4 in \(H_1\).
\(\star\) If there are two vertices of \(T\) of degree 4 that are not adjacent in \(G_b\), then these two vertices are centers of two edge-disjoint copies \(F_2\) and \(F_3\) of \(K_{1, 4}\) in \(H_1\). Since \(G_r\) has two edge-disjoint copies of \(K_{1, 4}\) in \(G_r\), it follows that \(G\) has five pairwise edge-disjoint monochromatic copies of \(K_{1, 4}\).
\(\star\) If every two vertices in \(T\) are adjacent in \(G_b\), then \(G_b[T]=K_4\) and so \(G_r[T]= \overline{K}_4\). Thus, there are four pairwise edge-disjoint copies of \(K_{1, 4}\) in \(G_r\). Since \(G_b\) has at least one copy of \(K_{1, 4}\), it follows that \(G\) has five pairwise edge-disjoint monochromatic copies of \(K_{1, 4}\). ◻
As we mentioned earlier, Theorem 3.3 is a consequence of Proposition 1.5 as well as Theorems 3.2 and 4.2. Knowing that \(ER_5(K_{1, 4})= 9\) now makes it easy to determine \(ER_6(K_{1, 4})\).
Theorem 4.3. \(ER_6(K_{1, 4})= 10\).
Proof. Since \(ER_6(K_{1, 4}) \le ER_5(K_{1, 4}) + 1=10\) by Theorem 4.2 and Observation 1.2, it remains to show that \(ER_6(K_{1, 4}) \ge 10\). Consider a red-blue coloring of \(G= K_{9}\) such that the degree sequence of the red subgraph \(G_r\) is \((5^8, 6)\) and so the degree sequence of the blue subgraph \(G_b\) is \((2, 3^8)\). Since \(\Delta(G_b) = 3\), there is no copy of \(K_{1, 4}\) in \(G_b\). Furthermore, the size of \(G_r\) is 23 and the size of six pairwise edge-disjoint copies of \(K_{1, 4}\) is 24. Thus, \(G_r\) does not contain six pairwise edge-disjoint copies of \(K_{1, 4}\). Hence, this red-blue coloring of \(G\) does not produce six pairwise edge-disjoint monochromatic copies of \(K_{1, 4}\). Therefore, \(ER_6(K_{1, 4}) \ge 10\) and so \(ER_6(K_{1, 4}) = 10\). ◻
We close this section by presenting lower bounds for \(ER_t(K_{1, n})\) where \(t \ge 5\) and \(n \ge 3\).
Theorem 4.4. For integers \(t\) and \(n\) where \(t \ge 5\) and \(n \ge 3\), let \(ER_t(K_{1, n})= k\).
(1) If \(k\) is even or \(n\) is odd, then \(ER_t(K_{1, n}) \ge \left\lceil \dfrac{n+\sqrt{n^2+8nt}}{2} \right\rceil.\)
(2) If \(k\) is odd and \(n\) is even, then \(ER_t(K_{1, n}) \ge \left\lceil \dfrac{n+\sqrt{n^2+8nt-4}}{2} \right\rceil.\)
Proof. Let \(ER_t(K_{1, n}) =k\). Then every red-blue coloring of \(G = K_k\) results in \(t\) pairwise edge-disjoint monochromatic copies of \(K_{1, n}\). We consider two cases, according to whether either (1) \(k\) is even or \(n\) is odd or (2) \(k\) is odd and \(n\) is even.
Case \(1\). \(k\) is even or \(n\) is odd. Then there is an \((n-1)\)-regular graph \(F\) of order \(k\). Consider a red-blue coloring of \(G\) such that the red subgraph is \(G_r=F\) and the blue subgraph is \(G_b=G-E(F)\). Since \(G_r\) is \((n-1)\)-regular, there is no red \(K_{1, n}\) in \(G\). Thus, \(G_b\) contains \(t\) pairwise edge-disjoint blue copies of \(K_{1, n}\). Let \(m_b\) be the size of \(G_b\). Since the size of \(F\) is \(k(n-1)/2\) and the size of \(K_{1, n}\) is \(n\), it follows that
\[m_b= {k \choose 2}-\dfrac{k(n-1)}{2} \ge nt.\]
Thus, \(k(k-1)-k(n-1) \ge 2nt\) or \(k^2-nk-2nt \ge 0\). Hence, \(k \ge \dfrac{n+\sqrt{n^2+8nt}}{2}\). Since \(k\) is an integer, \(k \ge \left\lceil \dfrac{n+\sqrt{n^2+8nt}}{2} \right\rceil.\)
Case \(2\). \(k\) is odd and \(n\) is even. Then there is a graph \(H\) of order \(k\) such that exactly \(k-1\) vertices of \(H\) have degree \(n-1\) and one vertex of \(H\) has degree \(n-2\). Consider a red-blue coloring of \(G\) such that the red subgraph is \(G_r=H\) and the blue subgraph is \(G_b=G-E(H)\). Since \(\Delta(G_r)= n-1\) there is no red \(K_{1, n}\) in \(G\). Thus, \(G_b\) contains \(t\) pairwise edge-disjoint blue copies of \(K_{1, n}\). Let \(m_b\) be the size of \(G_b\). Since the size of \(H\) is \(\dfrac{1}{2} [(k-1)(n-1) + (n-2)]\) and the size of \(K_{1, n}\) is \(n\), it follows that
\[m_b= {k \choose 2}-\dfrac{(k-1)(n-1) + (n-2)}{2} \ge nt.\]
Then \(k(k-1)-[(k-1)(n-1) + (n-2)] \ge 2nt\) or \(k^2 -nk+(1-2nt) \ge 0\). Hence, \(k \ge \dfrac{n+\sqrt{n^2+8nt-4}}{2}\). Since \(k\) is an integer, \(k \ge \left\lceil \dfrac{n+\sqrt{n^2+8nt-4}}{2} \right\rceil.\) ◻
From the results obtained thus far, we see that the lower bound in (1) of Theorem 4.4 is the exact value for \(ER_t(K_{1, 3})\) for \(t = 5, 6, 7\) and the lower bound in (2) of Theorem 4.4 is the exact value for \(ER_t(K_{1, 4})\) for \(t = 5, 6\). On the other hand, strict inequality holds for \(ER_t(K_{1, 5})\) for \(t = 5\). Therefore, finding improved bounds for \(ER_t(K_{1, n})\) for integers \(t \ge 5\) and \(n \ge 3\) would be valuable.