All missing Ramsey numbers for trees versus the four-page book

Roland Lortz^a , Ingrid Mengersen^b

r.lortz@tu-braunschweig.de, ingrid.mengersen@t-online.de

For the Ramsey number r(Tn, Bm), where Tⁿ denotes a tree of order n and B^m denotes the m-page book K² + Km, it is known that r(Tn, Bm) = 2n − 1 if n ≥ 3m − 3. In case of n < 3m − 3, r(Tn, Bm) has not been completely evaluated except for m ≤ 3. Here we determine the missing values of r(Tn, B4). Our results close one gap in the table of the Ramsey numbers r(Tn, G) for all trees Tⁿ and all connected graphs G of order six.

Keywords: Ramsey number, tree, book, small graph Mathematics Subject Classification: 05C55, 05D10

DOI: 10.5614/ejgta.2021.9.2.10

1. Introduction

For any connected graph G of order n and any graph H the Ramsey number r(G, H) satisfies

\[r(G, H) \ge (n-1)(\chi(H) - 1) + 1,\]

where χ(H) denotes the chromatic number of H. By applying this lower bound, due to Chvatal ´ and Harary [1], to a tree Tⁿ of order n and the m-page book B^m = K² + Km, we obtain that

\[r(T_n, B_m) \ge 2n - 1. \tag{1}\]

Received: 15 May 2020, Revised: 23 March 2021, Accepted: 13 April 2021.

^aTechnische Universitat Braunschweig, Institut f ¨ ur Analysis und Algebra, AG Algebra ¨ 38092 Braunschweig, Germany

^bMoorhuttenweg 2d, 38104 Braunschweig, Germany ¨

Erdos, Faudree, Rousseau and Schelp [3] showed that equality holds in (1) for a certain range ˝ of n and m, namely

\[r(T_n, B_m) = 2n - 1 \text{ if } n \ge 3m - 3.\] (2)

The case Tⁿ = Sn, the star of order n, had already been considered earlier by Rousseau and Sheehan [8] who also proved that, for n ≥ 2,

\[r(T_n, B_m) \ge \max\left\{ (k+2)(n-1) + 1, m+2\left\lfloor \frac{m-1}{k+1} \right\rfloor \right\} \text{ with } k = \left\lfloor \frac{m-1}{n-1} \right\rfloor, \tag{3}\]

and that equality holds for Tⁿ = Pn, the path of order n. For Tⁿ 6= Pn, which implies n ≥ 4, r(Tn, Bm) is not completely known if n < 3m − 3. In [8] it was shown that in case of n ≤ m the lower bound (3) also matches the exact value if n − 1 divides m − 1, in particular if n = m. Recently, further results concerning the case n ≤ m have been obtained by Zhang, Chen and Zhu [9]. For m ≤ 3 and n ≥ 4, r(Tn, Bm) is completely determined by (2) except for m = 3 where 4 ≤ n ≤ 5. The missing values of r(Tn, B3) can be found in [2] and [5]. In this paper we focus on the case m = 4. By the above mentioned results, the values of r(Tn, B4) are still missing for 5 ≤ n ≤ 8 if Tⁿ 6= Pn. Moreover, it is already known that r(S5, B4) = 11 and r(S8, B4) = 16 (see [4, 6, 8]). All remaining cases will be settled in this paper. Our results close one gap in the table of the Ramsey numbers r(Tn, G) for all trees Tⁿ and all connected graphs G of order six obtained in [6] and [7].

Some specialized notation will be used. The vertex set of a graph G is denoted by V (G). We write G⁰ ⊆ G if G⁰ is a subgraph of G. For U ⊆ V (Kn), [U] is the subgraph induced by U. A coloring of a graph always means a 2-coloring of its edges with colors red and green. An (F1, F2)-coloring is a coloring containing neither a red copy of F¹ nor a green copy of F2. Given a coloring of Kn, we define the r-degree dr(v) to be the number of red edges incident to v ∈ V (Kn). Moreover, ∆^r = maxv∈^V (Kn) dr(v). The set of vertices joined red to v is denoted by Nr(v). If U = {v1, v2, . . . , vs} ⊆ V (Kn), then we write Nr(U) or Nr(v1, v2, . . . , vs) instead of Nr(v1)∩Nr(v2)∩ . . . ∩ Nr(vs). Similarly we define dg(v), ∆g, Ng(v), Ng(U) and Ng(v1, v2, . . . , vs). Furthermore, [U]^r and [U]^g are the red and the green subgraphs induced by U. For disjoint subsets U1, U² ⊆ V (Kn), qr(U1, U2) denotes the number of red edges between U¹ and U² and qg(U1, U2) is defined similarly. If U¹ consists of a single vertex v, then we use qr(v, U2) and qg(v, U2) instead. Moreover, in case of v ∈ U, qr(v, U) and qg(v, U) mean qr(v, U \ {v}) and qg(v, U \ {v}), respectively. We write P^k = v1v² . . . v^k for the path P^k with vertices v1, v2, . . . , v^k and edges vivi+1 for i = 1, . . . , k − 1. Moreover, (v1v² . . . vk) denotes the cycle C^k obtained from P^k = v1v² . . . v^k by adding the edge v1vk. For k ≥ 2 and n ≥ k + 2, the broom Bn−k,k is defined as a tree of order n obtained by identifying the vertex of degree n−k of a star Sn−k+1 with an end-vertex of a path Pk.

2. The missing values of r(Tn, B4)

It follows from (2) that, for any tree Tn,

\[r(T_n, B_4) = 2n - 1 \text{ if } n \ge 9.\]

Moreover, as mentioned above, the lower bound (3) matches the exact value of r(Tn, Bm) for Tⁿ = Pⁿ and, if n = m, for any Tn. Using that Tⁿ = Pⁿ if n ≤ 3 we obtain

\[r(T_2, B_4) = 6, \quad r(T_3, B_4) = 7, \quad r(T_4, B_4) = 10,\] (4)

\[r(P_5, B_4) = 10\] and \(r(P_n, B_4) = 2n - 1\) if \(n \ge 6\). (5)

In the remaining case 5 ≤ n ≤ 8 and Tⁿ 6= Pⁿ the exact values of r(Tn, B4) apart from r(S5, B4) and r(S8, B4) are still missing and will be determined here. By (3) and (1) it is already known that

\[r(T_5, B_4) \ge 10\] and \(r(T_n, B_4) \ge 2n - 1\) if \(n \ge 6\). (6)

First we consider Tⁿ = Sn. The following theorem, where r(S5, B4) and r(S8, B4) are contained for the sake of completeness, shows that the values of r(Sn, B4) with 5 ≤ n ≤ 8 differ from the lower bounds in (6) except for n = 7.

Theorem 1. Let 5 ≤ n ≤ 8. Then

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

Proof. It remains to prove r(S6, B4) = 12 and r(S7, B4) = 13. The coloring of K¹¹ where [V ]^r = K³ ∪ H and H is obtained from a cycle (v1v² . . . v8) by adding the edges viv(i+2) mod ⁸ for i = 1, . . . , 8 yields r(S6, B4) ≥ 12, and (6) implies r(S7, B4) ≥ 13. To establish equality, assume that we have an (Sn, B4)-coloring χ of K^t with 6 ≤ n ≤ 7, where t = 12 if n = 6 and t = 13 if n = 7. First we derive some properties of χ useful in order to deduce a contradiction from our assumption. Let V denote the vertex set of K^t .

Claim 1. Let v ∈ V with U = Nr(v) and W = Ng(v), and let w ∈ W. Then

(i) \[q_g(w, W) \le 3\], (ii) \(7 \le d_g(v) \le n + 1\), (iii) \(q_g(w, U) \ge 3\), (iv) \(q_g(w, W) \ge 1\).

Proof of Claim 1. (i): If qg(w, W) > 3, then a green B⁴ with spine vw occurs, a contradiction.

(ii): Sⁿ 6⊆ [V ]^r forces ∆^r ≤ n − 2. Thus, dg(v) ≥ |V | − 1 − ∆^r ≥ 7 for every v ∈ V . To prove that dg(v) ≤ n + 1 consider a vertex v ^∗ ∈ V with dg(v ∗ ) = ∆g. Let U ^∗ = Nr(v ∗ ) and W^∗ = Ng(v ∗ ). Clearly, qg(w, W^∗ ) + qr(w, W^∗ ) = |W^∗ | − 1 = ∆^g − 1 for every w ∈ W^∗ . Using qr(w, W^∗ ) ≤ ∆^r ≤ n − 2 and (i) we obtain ∆^g − n + 1 ≤ qg(w, W^∗ ) ≤ 3. Hence ∆^g ≤ n + 2. Assume that ∆^g = n + 2, i.e. |W^∗ | = n + 2. Then qg(w, W^∗ ) = 3 for every w ∈ W^∗ . In case of n = 7 this implies [W^∗ ]^g to be a 3-regular graph of order 9, a contradiction. In case of n = 6, |V | = 12 and |W^∗ | = n+2 yield |U ∗ | = 3. Take w1, w² ∈ W^∗ with w1w² green. Since dg(wi) ≥ 7 and qg(wⁱ , W^∗ ) = 3, all edges between {w1, w2} and U ^∗ have to be green, i.e. U ^∗ ⊆ Ng(w1, w2). Moreover, v ^∗ ∈ Ng(w1, w2). But this gives a green B⁴ with spine w1w2, a contradiction. Thus, ∆^g ≤ n + 1, and the proof of (ii) is complete.

(iii) and (iv): By (ii), dg(w) ≥ 7. Furthermore, dg(w) = qg(w, W) + qg(w, U) + 1. Hence, (iii) is an immediate consequence of (i), and qg(w, U) ≤ |U| ≤ ∆^r ≤ n − 2 yields (iv).

Claim 2. If v ∈ V exists with dr(v) = 4 where U = Nr(v) and W = Ng(v), then

• (i) Ng(w1, w2) ∩ W = Nr(w1, w2) ∩ U = ∅ for any w1, w² ∈ W with w1w² green,
• (ii) qg(w, U) = 3 for every w ∈ W, (iii) [W]^g is 3-regular.

Proof of Claim 2. (i) and (ii): Consider w1, w² ∈ W joined green. B⁴ 6⊆ [V ]^g forces |Ng(w1, w2)| ≤ 3, and Claim 1(iii) implies |Ng(w1, w2) ∩ U| ≥ 2. Since v ∈ Ng(w1, w2), only Ng(w1, w2) ∩ W = ∅ and |Ng(w1, w2) ∩ U| = 2 is left. Consequently, qg(w1, U) = qg(w2, U) = 3 and Nr(w1, w2) ∩ U = ∅. Additionally we obtain (ii), as every w ∈ W is incident to at least one green edge in [W] by Claim 1(iv).

(iii): By Claim 1(ii), dg(w) ≥ 7 for any w ∈ W. Thus, (ii) and Claim 1(i) yield (iii).

Using Claims 1 and 2 now we deduce a contradiction from our above assumption.

• Case 1. n = 6. Consider some v ∈ V . Let W = Ng(v). Claim 1(ii) implies dg(v) = 7, i.e. |W| = 7, and we obtain dr(v) = 4 from |V | = 12. Thus, Claim 2(iii) forces [W]^g to be a 3-regular graph of order 7, a contradiction.
• Case 2. n = 7. By Claim 1(ii), 7 ≤ dg(v) ≤ 8 for every v ∈ V . Since |V | = 13, [V ]^g cannot be 7-regular. Consequently, a vertex v ^∗ ∈ V with dg(v ∗ ) = 8 and dr(v ∗ ) = 4 must occur. Let U = Nr(v ∗ ) and W = Ng(v ∗ ). If qr(u, W) = 2 for every u ∈ U, then dg(u) ≥ 7 implies qg(u, U) ≥ 1, and we find u1, u² ∈ U with u1u² green. But this yields a green B⁴ since |Ng(u1, u2) ∩ W| ≥ 4, a contradiction. As qr(U, W) = 8 by Claim 2(ii), it remains that a vertex u ^∗ ∈ U with qr(u ∗ , W) ≥ 3 exists. Let W⁰ ⊆ Nr(u ∗ ) ∩ W with |W⁰ | = 3 and let W⁰⁰ = W \ W⁰ . Claim 2(i) forces [W⁰ ] to be a red K3. One of the following two subcases must occur.
• Case 2.1. qg(w ∗ , W⁰ ) = 3 for some w ^∗ ∈ W⁰⁰. By Claim 2(i), u ∗w ^∗ has to be green and Claim 2(ii) yields two further vertices u 0 , u⁰⁰ ∈ U joined green to w ∗ . Since qg(u ∗ , W) ≤ 5 and dg(u ∗ ) ≥ 7, at least one of the vertices u 0 and u ⁰⁰, say u 0 , is joined green to u ∗ . Moreover, Claim 2(ii) implies that u ⁰w is green for every w ∈ W⁰ . But then W⁰ ∪ {u ^∗} ⊆ Ng(u 0 , w^∗ ) and we obtain a green B⁴ with spine u 0w ∗ , a contradiction.
• Case 2.2. qg(w, W⁰ ) ≤ 2 for every w ∈ W⁰⁰. By Claim 2(iii), [W]^g has to be 3-regular yielding qg(W⁰ , W⁰⁰) = 9. Consequently, since |W⁰⁰| = 5, qg(w ∗ , W⁰ ) = 1 for some w ^∗ ∈ W⁰⁰ and qg(w, W⁰ ) = 2 for every w ∈ W⁰⁰\{w ^∗}. Moreover, the 3-regularity of [W]^g implies qg(w ∗ , W⁰⁰) = 2 and qg(w, W⁰⁰) = 1 for every w ∈ W⁰⁰ \ {w ^∗}. Thus, the two red neighbors of w ∗ in W⁰⁰ have to be joined green. Furthermore, they must have at least one common green neighbor in W⁰ . This contradicts Claim 2(i), and we are done.

It remains to consider the non-star trees Tⁿ 6= Pⁿ with 5 ≤ n ≤ 8. The following theorem shows that r(Tn, B4) matches the bounds given in (6) for all these trees.

Theorem 2. Let 5 ≤ n ≤ 8 and let Tⁿ ∈ { / Pn, Sn}. Then

\[r(T_n, B_4) = 10 \text{ if } n = 5 \text{ and } r(T_n, B_4) = 2n - 1 \text{ if } n \ge 6.\]

Proof. Considering (6) it remains to prove \(r(T_5, B_4) \leq 10\) for \(T_5 \notin \{P_5, S_5\}\), i.e. \(T_5 = B_{2,3}\), and \(r(T_n, B_4) \leq 2n-1\) for every \(T_n \notin \{P_n, S_n\}\) with \(6 \leq n \leq 8\). Assume that we have a \((B_{2,3}, B_4)\)-coloring \(\chi\) of \(K_{10}\) or a \((T_n, B_4)\)-coloring \(\chi\) of \(K_{2n-1}\) for some \(T_n \notin \{P_n, S_n\}\) with \(6 \leq n \leq 8\). To deduce a contradiction from this assumption first we derive some properties of \(\chi\). Let V denote the vertex set of the complete graphs \(K_{10}\) and \(K_{2n-1}\). \(B_4 \not\subseteq [V]_g\) yields

Claim 3. If \(V' \subseteq V\) with \(|V'| \ge 2\) and \(|N_a(V')| \ge 4\), then [V'] is a red complete graph.

\(T_n \not\subseteq [V]_r\) forces \(K_n \not\subseteq [V]_r\). Consequently, Claim 3 immediately implies

Claim 4. If \(V' \subseteq V\) and \(|V'| \ge n\), then \(|N_q(V')| \le 3\).

In case of \(n \geq 6\) the restriction \(K_n \not\subseteq [V]_r\) can be improved.

Claim 5. If \(n \geq 6\), then \(K_{n-2} \not\subseteq [V]_r\).

Proof of Claim 5. Assume to the contrary that \(K_{n-2}\subseteq [V]_r\). Let U be the vertex set of a red \(K_{n-2}\) and let \(W=V\setminus U\). Since \(|U|\geq 4\) and |W|=n+1, Claim 4 implies \(q_r(U,W)\geq 1\). Consider two vertices \(u\in U\) and \(w\in W\) where uw is red. Let \(W'=W\setminus \{w\}\). Again using Claim 4 we obtain that \(q_r(U,W')\geq 1\). A red edge u'w' with \(u'\in U\setminus \{u\}\) and \(w'\in W'\) cannot occur: otherwise, since any non-star tree contains two different vertices adjacent to vertices of degree 1, the red \(K_{n-2}\) together with the red edges uw and u'w' would give every \(T_n\neq S_n\) in red, a contradiction. It remains that uw' is red for some \(w'\in W'\) and that \(U\setminus \{u\}\subseteq N_g(W')\). But this contradicts Claim 4 if \(n\geq 7\), and in case of n=6, \(U\setminus \{u\}=N_g(W')\) is left. Thus, \(q_r(w,W')\geq 1\). But then we find any \(T_6\) in red, since every \(T_6\) contains a vertex adjacent to two vertices of degree 1 or a vertex of degree 1 adjacent to a vertex of degree 2. This contradiction completes the proof of Claim 5.

Applying Claims 3 and 5 we obtain an improvement of Claim 4 for \(n \ge 6\).

Claim 6. If \[n \ge 6\] and if \(V' \subseteq V\) with \(|V'| \ge n - 2\), then \(|N_g(V')| \le 3\).

Using Claims 3 to 6 now we deduce a contradiction from the above assumption. Since \(T_n \notin \{P_n, S_n\}\), the maximum degree \(\Delta(T_n)\) satisfies \(3 \le \Delta(T_n) \le n-2\). We distinguish the following four cases depending on \(\Delta(T_n)\) and use \(T_{n,k}\) to denote a tree \(T_n\) with \(\Delta(T_n) = k\).

Case 1. \(\Delta(T_n)=n-2\) where \(5\leq n\leq 8\). There is exactly one tree \(T_{n,n-2}\), namely the broom \(B_{n-3,3}\). By Theorem 1 and (4), \(S_{n-1}\subseteq [V]_r\). Consider a red \(S_{n-1}\) in \(\chi\) with vertex set U and \(u^*\) as vertex of degree n-2. Let \(W=V\setminus U\). Since \(|W|\geq n\) and \(|U|\geq 4\), Claim 4 yields \(q_r(U,W)\geq 1\). If uw is red for some \(u\in U\setminus \{u^*\}\) and some \(w\in W\), then a red \(B_{n-3,3}\) occurs, a contradiction. Otherwise, \(u^*w\) is red for some \(w\in W\) and \(N_g(U\setminus \{u^*\})=W\). Using Claim 3 we obtain that \([U\setminus \{u^*\}]\) is a red \(K_{n-2}\) contradicting Claim 5 for \(n\geq 6\). If n=5, then [U] is a red \(K_4\) yielding a red \(B_{2,3}\) together with \(u^*w\), a contradiction, and we are done.

Case 2. \(\Delta(T_n) = n-3\) where \(6 \le n \le 8\). There are three trees \(T_{n,n-3}\), namely \(T_{n,n-3}^{(1)}\) and \(T_{n,n-3}^{(2)}\) obtained from \(S_{n-2}\) by adding two vertices of degree 1 joined to the same vertex of degree 1 or to two different vertices of degree 1 of \(S_{n-2}\), respectively, and \(T_{n,n-3}^{(3)} = B_{n-4,4}\) (for n=7 these three trees \(T_{n,n-3}\) are shown in Figure 1). Now we consider a red \(S_{n-2}\) in \(\chi\) with vertex set U and \(u^*\) as vertex of degree n-3. Let \(U\setminus\{u^*\}=\{u_1,\ldots,u_{n-3}\}\) and \(W=V\setminus U=\{w_1,\ldots,w_{n+1}\}\). By Claim 5, a green edge, say \(u_1u_2\), must occur in [U]. Since

Figure 1. The trees \(T_{7,4}\) with vertex labeling.

\(B_4 \not\subseteq [V]_g\), there are at most three common green neighbors of \(u_1\) and \(u_2\) in W, and we may assume that any \(w \in W \setminus \{w_{n-1}, w_n, w_{n+1}\}\) is joined red to \(u_1\) or to \(u_2\). This implies that, without loss of generality, \(u_1w_1\) and \(u_1w_2\) are red. Thus, \(T_{n,n-3}^{(1)}\) is unavoidable in \([V]_r\). If \(T_{n,n-3}^{(2)} \not\subseteq [V]_r\), then there are only green edges between \(\{u_2,\ldots,u_{n-3}\}\) and W. Consequently, all edges from \(u_1\) to \(\{w_1,\ldots,w_{n-2}\}\) have to be red. If there are only green edges in \([\{w_1,\ldots,w_{n-2}\}]\), then four vertices from \(\{w_1,\ldots,w_{n-2}\}\) and two vertices from \(\{u_2,\ldots,u_{n-3}\}\) yield a green \(K_6-e\supseteq B_4\), a contradiction. Hence we may assume that \(w_1w_2\) is red. But this yields a red \(T_{n,n-3}^{(2)}\) with \(u_1\) as vertex of degree n-3, a contradiction. Finally, if \(T_{n,n-3}^{(3)} \not\subseteq [V]_r\), then in [W] all edges incident to \(w_1\) or to \(w_2\) have to be green yielding a green \(B_4\), a contradiction.

Figure 2. The trees \(T_{n,n-3}\) with \(7 \le n \le 8\).

Case 3. \(\Delta(T_n)=n-4\) where \(7\leq n\leq 8\). The five trees \(T_{7,3}\) and the seven trees \(T_{8,4}\) are shown in Figure 2. We may use that \(T_{6,3}^{(1)}\), every \(T_{7,4}\) and also \(P_7\) must occur in \([V]_r\) (see Case 2 and (5)). If a red \(T_{7,4}\) in \(\chi\) with \(U=V(T_{7,4})\) is considered, then the vertices in U shall be denoted by \(u_1,u_2,\ldots,u_7\) as in Figure 1 and W means \(V\setminus U\).

\(\bullet\) \(T_7 \in \{T_{7,3}{}^{(1)}, T_{7,3}{}^{(2)}\}\). Consider a red \(P_7 = u_1u_2 \dots u_7\) in \(\chi\). Let \(W = V \setminus \{u_1, \dots, u_7\}\). If \(T_{7,3}{}^{(1)} \not\subseteq [V]_r\), then \(\{u_2, u_3, u_5, u_6\} \subseteq N_g(W)\) contradicting Claim 6. If \(T_{7,3}{}^{(2)} \not\subseteq [V]_r\), then \(u_3u_5\) and all edges between \(\{u_3, u_5\}\) and W have to be green contradicting \(B_4 \not\subseteq [V]_g\).

• \(T_7 = T_{7,3}{}^{(3)}\). Consider a red \(T_{6,3}{}^{(1)}\) in \(\chi\). Let U be the set of the four vertices of degree 1 of \(T_{6,3}{}^{(1)}\) and \(W = V \setminus V(T_{6,3}{}^{(1)})\). \(T_{7,3}{}^{(3)} \not\subseteq [V]_r\) forces \(U \subseteq N_g(W)\) contradicting Claim 6.
• \(T_7 \in \{T_{7,3}^{(4)}, T_{7,3}^{(5)}\}\). Consider a red \(T_{7,4}^{(2)}\) in \(\chi\). If \(T_{7,3}^{(4)} \not\subseteq [V]_r\), then \(q_r(u_1, W \cup \{u_3, u_6\}) \le 1\) and \(q_r(u_3, W \cup \{u_1, u_5\}) \le 1\). Thus, \(u_1\) and \(u_3\) have at least four common green neighbors in W, and \(B_4 \not\subseteq [V]_g\) forces \(u_1u_3\) to be red. Consequently, \(u_3u_5\), \(u_1u_6\) and all edges between \(\{u_1, u_3\}\) and W have to be green. But then \(B_4 \not\subseteq [V]_g\) implies \(q_r(u_i, W) \ge 3\) for i = 5, 6 yielding a red \(T_{7,3}^{(4)}\), a contradiction. If \(T_{7,3}^{(5)} \not\subseteq [V]_r\), then \(u_2u_4\) and all edges between \(\{u_2, u_4\}\) and W have to be green contradicting \(B_4 \not\subseteq [V]_g\).
• \(T_8 \in \{T_{8,4}^{(1)}, T_{8,4}^{(2)}\}\). Consider a red \(T_{7,4}^{(2)}\) in \(\chi\). If \(T_{8,4}^{(1)} \not\subseteq [V]_r\), then all edges between \(\{u_1, u_3\}\) and W have to be green. Since \(B_4 \not\subseteq [V]_g\), \(u_1u_3\) has to be red, and Claim 6 demands at least one red edge from W to \(\{u_2, u_4\}\). But this gives a red \(T_{8,4}^{(1)}\), a contradiction. If \(T_{8,4}^{(2)} \not\subseteq [V]_r\), then all edges between \(\{u_2, u_4\}\) and W have to be green, and this forces \(u_2u_4\) to be red. Consequently, all edges from \(u_7\) to W have to be green, and Claim 6 yields three vertices \(w_1, w_2, w_3 \in W\) joined red to \(u_3\). Moreover, \(B_4 \not\subseteq [V]_g\) implies \(q_r(w_i, W \setminus \{w_1, w_2, w_3\}) \ge 2\) for \(1 \le i \le 3\). But then we obtain a red \(T_{8,4}^{(2)}\) with \(u_3\) as vertex of degree 4, a contradiction.
• \(T_8 = T_{8,4}{}^{(3)}\). Consider a red \(T_{7,4}{}^{(3)}\) in \(\chi\). If \(T_{8,4}{}^{(3)} \not\subseteq [V]_r\), then all edges from \(u_3\) to W are green and \(q_r(u_i,W) \leq 2\) for \(i \in \{1,2,4\}\). Hence, since \(B_4 \not\subseteq [V]_g\), \([\{u_1,u_2,u_3,u_4\}]\) has to be a red \(K_4\), and \(T_{8,4}{}^{(3)} \not\subseteq [V]_r\) forces \(\{u_5,u_6,u_7\} \subseteq N_g(W)\). But then the eight vertices in W have four common green neighbors, a contradiction to Claim 6.

Figure 3. Two trees \(T_8\) with vertex labeling.

• \(T_8 = T_{8,4}{}^{(4)}\). From above we already know that \(T_{8,4}{}^{(2)} \subseteq [V]_r\). Consider a red \(T_{8,4}{}^{(2)}\) in \(\chi\) where the vertices are denoted as in Figure 3. Let \(W = V \setminus \{u_1, \ldots, u_8\}\). If \(T_{8,4}{}^{(4)} \not\subseteq [V]_r\), then \(\{u_5, u_6, u_7\} \subseteq N_g(W)\) and \(q_r(u_4, W) \le 1\). Thus, we find six vertices in W with four common green neighbors in U, a contradiction to Claim 6.
• \(T_8 \in \{T_{8,4}^{(5)}, T_{8,4}^{(6)}, T_{8,4}^{(7)}\}\). Consider a red \(T_{7,4}^{(1)}\) in \(\chi\). If \(T_{8,4}^{(5)} \not\subseteq [V]_r\), then \(q_r(\{u_3, u_4\}, W) = 0\), and \(B_4 \not\subseteq [V]_g\) forces \(u_3u_4\) to be red. Consequently, \(q_r(u_6, W) = 0\) and \(q_r(u_1, W) \le 0\). But then we find six vertices in W with four common green neighbors in U, a contradiction to Claim 6. If \(T_{8,4}^{(6)} \not\subseteq [V]_r\), then \(q_r(u_i, W) \le 1\) for i = 3, 4 and \(q_r(u_i, W) \le 2\) for i = 1, 2, 5. Since \(B_4 \not\subseteq [V]_g\), \([\{u_1, u_2, u_3, u_4, u_5\}]\) has to be a red \(K_5\). Moreover, \(T_{8,4}^{(6)} \not\subseteq [V]_r\) forces \(q_r(\{u_6, u_7\}, W) = 0\), and there are six vertices in W with four common green neighbors in U contradicting Claim 6. Finally, if \(T_{8,4}^{(7)} \not\subseteq [V]_r\), then \(q_r(u_6, W) = 0\) and \(q_r(u_i, W) \le 2\) for i = 1, 2, 5. Hence \(B_4 \not\subseteq [V]_g\) forces \([\{u_1, u_2, u_5, u_6, u_7\}]\) to be a red \(K_5\). Moreover, \(T_{8,4}^{(7)} \not\subseteq [V]_r\) implies \(q_r(u_i, W) = 0\) for i = 1, 2, 5, 6, 7 and we find eight vertices in W with five common green neighbors in U, another contradiction to Claim 6.

Figure 4. The trees \(T_{8,3}\).

Case 4: \(\Delta(T_n) = n - 5\) where n = 8. The ten trees \(T_{8,3}\) are shown in Figure 4. We may use that \(P_8\) and \(T_{7,3}^{(i)}\) for \(i \in \{3,4,5\}\) occur in \([V]_r\) (see (5) and Case 3). If a red \(T_{7,3}^{(i)}\) in \(\chi\) with \(U = V(T_{7,3}^{(i)})\) is considered, then the vertices in U shall be denoted as in Figure 5 and W means \(V \setminus U\).

• \(T_8 \in \{T_{8,3}^{(1)}, T_{8,3}^{(2)}, T_{8,3}^{(3)}\}\). Consider a red \(P_8 = u_1u_2 \dots u_8\) in \(\chi\). Let \(W = V \setminus \{u_1, \dots, u_8\}\). If \(T_{8,3}^{(1)} \not\subseteq [V]_r\), then \(\{u_2, u_3, u_6, u_7\} \subseteq N_g(W)\), and \(T_{8,3}^{(2)} \not\subseteq [V]_r\) forces that \(\{u_3, u_4, u_5, u_6\} \subseteq N_g(W)\), both cases contradicting Claim 6. If \(T_{8,3}^{(3)} \not\subseteq [V]_r\), then \(u_3u_5\), \(u_4u_6\) and all edges between W and \(\{u_4, u_5\}\) are green. Hence, by Claim 6, \(q_r(\{u_1, u_8\}, W) \ge 1\), and we may assume that \(u_1w^*\) for some \(w^* \in W\) is red. But this forces all edges from \(u_3\) to \(W \setminus \{w^*\}\) to be green yielding a green \(B_4\), a contradiction.

Figure 5. Some trees \(T_{7,3}\) with vertex labeling.

• \(T_8 \in \{T_{8,3}^{(4)}, T_{8,3}^{(5)}\}\). Consider a red \(T_{7,3}^{(4)}\) in \(\chi\). If \(T_{8,3}^{(4)} \not\subseteq [V]_r\), then \(q_r(u_i, W) \le 1\) for i=1,2,6,7, and \(B_4 \not\subseteq [V]_g\) implies that \([\{u_1,u_2,u_6,u_7\}]\) is a red \(K_4\). By Claim 6, \(q_r(\{u_1,u_2,u_6,u_7\},W) \ge 1\), and we may assume that \(u_1w^*\) for some \(w^* \in W\) is red. But this yields a red \(T_{8,3}^{(4)}\), a contradiction. If \(T_{8,3}^{(5)} \not\subseteq [V]_r\), then \(\{u_1,u_2,u_6,u_7\} \subseteq N_g(W)\) contradicting Claim 6.

• \(T_8 = T_{8,3}{}^{(6)}\). Consider a red \(T_{7,3}{}^{(5)}\) in \(\chi\). If \(T_{8,3}{}^{(6)} \not\subseteq [V]_r\), then \(\{u_1, u_5, u_7\} \subseteq N_g(W)\). Since \(B_4 \not\subseteq [V]_g\), \([\{u_1, u_5, u_7\}]\) is a red \(K_3\), and Claim 6 forces \(q_r(u_2, W) \ge 1\). But then we find a red

\(T_{8.3}^{(6)}\) with \(u_5\) as vertex of degree 3, a contradiction.

• \(T_8 = T_{8,3}^{(7)}\). Consider a red \(T_{7,3}^{(3)}\) in \(\chi\). If \(T_{8,3}^{(7)} \not\subseteq [V]_r\), then \(q_r(u_7,W) = 0\). Moreover, \(B_4 \not\subseteq [V]_g\) implies that \(q_r(w,W) \ge 4\) for every \(w \in W\). Hence, as \(T_{8,3}^{(7)} \not\subseteq [V]_r\), \(q_r(u_4,W) = 0\) and \(q_r(u_3,W) \le 1\). But then Claim 6 forces \(q_r(u_i,W) \ge 2\) for i=1,2, and this yields a red \(T_{8,3}^{(7)}\), a contradiction.
• \(T_8 \in \{T_{8,3}^{(8)}, T_{8,3}^{(9)}, T_{8,3}^{(10)}\}\). From above we already know that \(T_{8,3}^{(7)} \subseteq [V]_r\). Consider a red \(T_{8,3}^{(7)}\) in \(\chi\) where the vertices are denoted as in Figure 3. Let \(W = V \setminus \{u_1, \ldots, u_8\}\). If \(T_{8,3}^{(8)} \not\subseteq [V]_r\), then \(u_6u_8\) and all edges between \(\{u_6, u_8\}\) and W have to be green. But this yields a green \(B_4\), a contradiction. If \(T_{8,3}^{(9)} \not\subseteq [V]_r\), then \(q_r(\{u_1, u_2\}, W) = 0\), and \(B_4 \not\subseteq [V]_g\) implies that \(u_1u_2\) is red. Hence \(q_r(u_3, W) = 0\), and, by Claim 6, a red edge \(u_4w^*\) with \(w^* \in W\) must occur. Moreover, \(B_4 \not\subseteq [V]_g\) implies \(q_r(w, W) \geq 3\) for every \(w \in W\). But then we find a red \(T_{8,3}^{(9)}\) in \([\{u_4, u_5, u_6, u_7, w^*, w_1, w_2, w_3\}]\) where \(w_1\) and \(w_2\) are red neighbors of \(w^*\) in W and \(w_3\) is a red neighbor of \(w_2\) in W different from \(w^*\) and \(w_1\), a contradiction. Finally, if \(T_{8,3}^{(10)} \not\subseteq [V]_r\), then \(q_r(\{u_5, u_7\}, W) = 0\). Hence \(B_4 \not\subseteq [V]_g\) implies that \(u_5u_7\) is red. Consequently, \(q_r(u_4, W) = 0\), and, by Claim 6, \(q_r(u_1, W) \geq 2\). But this yields a red \(T_{8,3}^{(10)}\) in \([\{u_1, u_2, u_3, u_4, u_5, u_7, w_1, w_2\}]\) where \(w_1\) and \(w_2\) are red neighbors of \(u_1\) in W, a contradiction, and the proof of Theorem 2 is complete.

References

• [1] V. Chvátal and F. Harary, Generalized Ramsey theory for graphs III: Small off-diagonal numbers, Pacific J. Math. 41 (1972), 335–345.
• [2] M. Clancy, Some small Ramsey numbers, J. Graph Theory 1 (1977), 89–91.
• [3] P. Erdős, R.J. Faudree, C.C. Rousseau and R.H. Schelp, The book-tree Ramsey numbers, Sci. Ser. A Math. Sci. (N.S) 1 (1988), 111–117.
• [4] G. Hua, S. Hongxue and L. Xiangyang, Ramsey numbers \(r(K_{1,4}, G)\) for all three-partite graphs G of order six, J. Southeast Univ. (English Ed.) 20 (2004), 378–380.
• [5] G.R.T. Hendry, Ramsey numbers for graphs with five vertices, J. Graph Theory 13 (1989), 245–248.
• [6] R. Lortz and I. Mengersen, On the Ramsey numbers for stars versus connected graphs of order six, Australas. J. Combin. 73 (2019), 1–24.
• [7] R. Lortz and I. Mengersen, On the Ramsey numbers for non-star trees versus connected graphs of order six, Discuss. Math. Graph Theory, to appear.
• [8] C.C. Rousseau and J. Sheehan, A class of Ramsey problems involving trees, J. London Math. Soc.(2) 18 (1978), 392–396.
• [9] L. Zhang, K. Chen and D. Zhu, Some tree-book Ramsey numbers, Ars Combin. 130 (2017), 97–102.