For every connected graph \(F\) with \(n\) vertices and every graph \(G\) with chromatic surplus \(s(G)\leq n\), the Ramsey number \(r(F,G)\) satisfies \(
r(F,G) \geq (n-1)(\chi(G)-1) + s(G), \) where \(\chi(G)\) denotes the chromatic number of \(G\). If this lower bound is attained, then \(F\) is called \(G\)-good. For all connected graphs \(G\) with at most six vertices and \(\chi(G) \geq 4\), every tree \(T_n\) of order \(n\geq 5\) is \(G\)-good. In case of \(\chi(G) = 3\) and \(G \neq K_6-3K_2\), every non-star tree \(T_n\) is \(G\)-good except for some small \(n\), whereas \(r(S_n,G)\) for the star \(S_n = K_{1,n-1}\) in a few cases differs by at most 2 from the lower bound. In this note, we prove that the values of \(r(S_n,K_6-3K_2)\) are considerably larger for sufficiently large \(n\). Furthermore, exact values of \(r(S_n,K_6-3K_2)\) are obtained for small \(n\).
Let \(G\) be a graph with chromatic number \(\chi(G)\). The chromatic surplus \(s(G)\) is defined to be the smallest number of vertices in a color class under any \(\chi(G)\)-coloring of the vertices of \(G\). It is well-known (cf. [3]) that for any connected graph \(F\) with \(n\) vertices and any graph \(G\) with \(s(G) \le n\) the Ramsey number \(r(F,G)\) satisfies \[\label{lowerbound} r(F,G) \ge (n-1)(\chi(G)-1) + s(G). \tag{1}\]
When equality occurs in (1), \(F\) is said to be \(G\)-good. The concept of \(G\)-goodness generalizes a classical result of Chvátal [2] who proved that \(r(T_n,K_m) = (n-1)(m-1)+1\) for any tree \(T_n\) with \(n\) vertices. Results concerning the \(G\)-goodness of trees have been obtained for various classes of graphs \(G\) and also for small graphs \(G\). The Ramsey number \(r(T_n,G)\) for connected graphs \(G\) with at most \(5\) vertices was studied in [3], \(r(T_n,G)\) for connected graphs with six vertices was investigated in [7] and [5]. These results show that every tree \(T_n\) with \(n\ge 5\) is \(G\)-good if \(G\) is a connected graph with at most six vertices and \(\chi(G) \ge 4\). In case of \(\chi(G) = 3\) and \(G \neq K_6-3K_2\) every non-star tree \(T_n\) is \(G\)-good except for some small \(n\), whereas \(r(S_n,G)\) for the star \(S_n=K_{1,n-1}\) in a few cases differs by at most 2 from the lower bound (1). For graphs \(G\) with \(\chi(G) = 2\) and at most six vertices the values of \(r(T_n,G)\) are not completely determined, but it is known that for some \(G\), especially for non-star complete bipartite graphs, they differ considerably from the lower bound (1) (see [1,6,8]). Here we will prove that also the values of \(r(S_n,K_6-3K_2)\) are much larger. We present a lower bound for \(r(S_n,K_6-3K_2)\) depending on \(r(S_n,C_4)\) which implies that \(r(S_n,K_6-3K_2) \ge 2n + \left\lfloor\sqrt{n-1\,}\right\rfloor – 1\) if \(n = q^2 + 1\) or \(n=q^2+2\) where \(q\) is any prime power and that \(r(S_n,K_6-3K_2) >2n-2 + \left\lfloor \sqrt{n-1\,} – 6 (n-1)^{11/40}\right\rfloor\) for all sufficiently large \(n\). For \(n \le 10\), our lower bound matches the exact value of \(r(S_n,K_6-3K_2)\) or differs from it by at most \(1\).
Some specialized notation will be used. A coloring of a graph always means a 2-coloring of its edges with colors red and green. An \((F_1,F_2)\)-coloring is a coloring containing neither a red copy of \(F_1\) nor a green copy of \(F_2\). We use \(V\) to denote the vertex set of \(K_n\) and define \(d_r(v)\) to be the number of red edges incident to \(v \in V\) in a coloring of \(K_n\). Moreover, \(\Delta_r = \max_{v \in V} d_r(v)\). The set of vertices joined red to \(v\) is denoted by \(N_r(v)\). Similarly we define \(d_g(v)\), \(\Delta_g\) and \(N_g(v)\). For \(U \subseteq V(K_n)\), the subgraph induced by \(U\) is denoted by \([U]\). Furthermore, \([U]_r\) and \([U]_g\) denote the red and the green subgraph induced by \(U.\) We write \(G'\subseteq G\) if \(G'\) is a subgraph of \(G\). For disjoint subsets \(U_1,U_2 \subseteq V(K_n)\), \(q_r(U_1,U_2)\) denotes the number of red edges between \(U_1\) and \(U_2\), and \(q_g(U_1,U_2)\) is defined similarly.
The following theorem establishes a general lower bound for \(r(S_n, K_6-3K_2)\) depending on \(r(S_n,C_4)\).
Theorem 2.1. Let \(n \ge 2\). Then \[r(S_n, K_6-3K_2) \ge r(S_n,C_4) + \left\{\begin{array}{ll}n-1 & \mbox{if\/ $n$ is odd,}\\ n &\mbox{if\/ $n$ is even.} \end{array} \right.\]
Proof. Let \(m = r(S_n,C_4) – 1\). Take an \((S_n,C_4)\)-coloring of \(K_m\). For \(n\) odd, add a red \(K_{n-1}\), and, for \(n\) even, a \(K_{n}\) with \(n/2\) independent green edges and all other edges colored red. Join the vertices of the \(K_m\) and the vertices of the \(K_{n-1}\) or \(K_n\), respectively, by green edges. Obviously, no red \(S_n\) occurs. Now consider any subgraph \(H\) of order six. If at least four vertices of \(H\) belong to the \(K_m\), then a green \(K_6-3K_2 \subseteq H\) is impossible since deleting any two vertices of a \(K_6-3K_2\) leaves a graph of order four containing a \(C_4\). Otherwise, at least three vertices of \(H\) belong to the \(K_{n-1}\) or \(K_n\). Then adjacent red edges occur in \(H\) and again a green \(K_6-3K_2 \subseteq H\) is impossible. Thus, the lower bound is established. ◻
Exact results on the values of \(r(S_n,C_4)\) are known only in special cases. Parsons [6] proved that \(r(S_n,C_4) = n + \left\lfloor\sqrt{n-1\,}\right\rfloor\) if \(n = q^2 + 1\) or \(n=q^2+2\) where \(q\) is any prime power. Burr, Erdös, Faudree, Rousseau and Schelp [1] showed that \(r(S_n,C_4) >n-1 + \left\lfloor \sqrt{n-1\,} – 6 (n-1)^{11/40}\right\rfloor\) for all sufficiently large \(n\). From these results and Theorem 2.1 we obtain the following lower bounds on \(r(S_n,K_6-3K_2)\) .
Corollary 2.2. (i) Let \(n = q^2 + 2\) where \(q\) is any power of \(2\) or \(n = q^2 + 1\) where \(q\) is any odd prime power. Then \[r(S_n,K_6-3K_2) \ge 2n + \left\lfloor \sqrt{n-1\,}\right\rfloor.\]
(ii) Let \(n = q^2 + 1\) where \(q\) is any power of \(2\) or \(n = q^2 + 2\) where \(q\) is any odd prime power. Then \[r(S_n,K_6-3K_2) \ge 2n -1 + \left\lfloor \sqrt{n-1\,}\right\rfloor.\]
(iii) If \(n\) is sufficiently large, then \[r(S_n,K_6-3K_2) > 2n -2 + \left\lfloor \sqrt{n-1\,} – 6 (n-1)^{11/40}\right\rfloor.\]
Using recent results on \(r(S_n,C_4)\) of Wu Yali, Sun Yongqi, Zhang Rui and Radziszowski [8], further lower bounds on \(r(S_n,K_6-3K_2)\) can be obtained from Theorem 2.1. The next theorem shows that the lower bound for \(r(S_n, K_6-3K_2)\) given in Theorem 2.1 matches the exact value of the Ramsey number if \(n\le 6\) or \(n=8\) and differs by at most 1 from it if \(n=7\) or \(9 \le n \le 10\). The value of \(r(S_5, K_6-3K_2)\) has already been obtained by Gu Hua, Song Hongxue and Liu Xiangyang [4] using a different method.
Theorem 2.3. \[\begin{array}{c|ccccccccc} n&\;2\;&\;3\;&4&5&6&7&8&9&10\\ \hline r(S_n,K_6-3K_2)&6&6&10&11&14&15/16&19&20/21&23/24 \end{array}\, .\]
The proof of Theorem 2.3 is based on the following lemmas.
Lemma 2.4. The red subgraph of an \((S_4, K_6-3K_2)\)-coloring of \(K_9\) is isomorphic to \(K_1 \cup 2C_4\) or to \(C_4 \cup C_5\).
Proof. \(S_4 \not\subseteq [V]_r\) implies \(\Delta_r \le 2\). Thus, every component of \([V]_r\) has to be a path or a cycle. If the union of all paths in \([V]_r\) contains at least three vertices, then it is a subgraph of a cycle. Moreover, \(2K_1 \subseteq K_2\). Hence, \([V]_r \subseteq H\) where \(H \in \{C_9,\; C_3 \cup C_6,\; C_4 \cup C_5, \; 3C_3, \; K_2 \cup C_7, \; K_2 \cup C_3 \cup C_4, \; K_1\cup C_8, \; K_1\cup C_3 \cup C_5, \; K_1\cup 2C_4\}\). Except for \([V]_r = H = K_1\cup 2C_4\) or \([V]_r = H = C_4 \cup C_5\) we find a forbidden \(K_6 – 3K_2\) in \([V]_g\). ◻
Lemma 2.5. \(r(S_4,K_6-3K_2) \le 10\).
Proof. Assume that an \((S_4,K_6-3K_2)\)-coloring of \(K_{10}\) exists. Delete one vertex \(v \in V\). By Lemma 2.4, the red subgraph of \([V\setminus \{v\}]\) has to be isomorphic to \(K_1 \cup 2C_4\) or to \(C_4 \cup C_5\). Moreover, \(\Delta_r \le 2\) forces only green edges from \(v\) to the vertices of \(V \setminus \{v\}\) belonging to a red cycle. Thus, in both cases we find a green \(K_6-3K_2\), a contradiction. ◻
Lemma 2.6. \(r(S_6,K_6-3K_2) \le 14\).
Proof.Assume that we have an \((S_6,K_6-3K_2)\)-coloring of \(K_{14}\). This implies \(\Delta_r \le 4\) and \(W_4 = K_5 – 2K_2 \subseteq [V]_g\) because \(r(S_6,W_4) = 13\) (see [3]). We distinguish three cases.
Case 1.\(K_5 \subseteq [V]_g\). For any \(K_5 \subseteq [V]_g\) with vertex set \(U\) and any two vertices \(w,w' \in V \setminus U\) joined green with \(q_r(w,U) = q_r(w',U) =2\) the following property \(pr(w,w',U)\) must be fulfilled: \(|N_r(w) \cap N_r(w') \cap U| \in \{0,2\}\). Otherwise \(w\) and \(w'\) would have exactly one common red neighbor \(u \in U\) and this would yield \(K_6 – 3K_2 \subseteq [(U \setminus \{u\}) \cup \{w,w'\} ]_g\), a contradiction. We distinguish two subcases.
Subcase 1.1. \(2K_5 \subseteq [V]_g\). Let \(U_1\) and \(U_2\) be the vertex sets of two vertex-disjoint green copies of \(K_5\) and let \(W = V \setminus (U_1 \cup U_2)\). Then \(K_6-3K_2 \not\subseteq [V]_g\) forces \(q_r(w,U_1) \ge 2\) and \(q_r(w,U_2) \ge 2\) for every \(w \in W\). Using \(\Delta_r \le 4\), we obtain that \(q_r(w,U_1) = q_r(w,U_2) =2\) for every \(w \in W\), \(q_r(W,U_1) = q_r(W,U_2)=8\) and \([W]_g = K_4\). Moreover, \(K_6-3K_2 \not\subseteq [V]_g\) forces \(q_r(u,U_1)\ge 2\) for every \(u\in U_2\) and \(q_r(u,U_2)\ge 2\) for every \(u\in U_1\). Thus, \(\Delta_r \le 4\) implies \(q_r(u, W) \le 2\) for every \(u \in U_1 \cup U_2\). If there are vertices \(u_1 \in U_1\) and \(u_2 \in U_2\) such that \(q_r(u_1,W) = q_r(u_2,W) = 0\), then \(K_6 – 3K_2\subseteq [W \cup \{u_1,u_2\}]_g\), a contradiction. Thus we may assume that \(q_r(u,W) \ge 1\) for every \(u \in U_1\). Since \(q_r(u, W) \le 2\) for every \(u \in U_1\) and \(q_r(W,U_1)=8\) there must be two vertices \(u_1\) and \(u_2\) in \(U_1\) with \(q_r(u_1,W)= q_r(u_2,W) = 1\), and \(q_r(u,W) = 2\) for every \(u \in U_1\setminus \{u_1,u_2\}\). Hence, the bipartite graph \([W\cup U_1]_r\) is isomorphic to \(C_6 \cup P_3\), to \(C_4 \cup P_5\) or to \(P_9\). In all three cases we find two vertices \(w_1,w_2 \in W\) with exactly one common red neighbor \(u \in U_1\), contradicting \(pr(w_1,w_2,U_1)\).
Subcase 1.2. \(K_5 \subseteq [V]_g\) and \(2K_5 \not\subseteq [V]_g\). Let \(U=\{u_1, \ldots , u_5\}\) be the vertex set of a green \(K_5\) and let \(W = V \setminus U\). Since \(K_6-3K_2 \not\subseteq [V]_g\), \(q_r(w,U) \ge 2\) for every \(w \in W\). Thus, \(\Delta_r \le 4\) forces only vertices of degree less or equal \(2\) in \([W]_r\). As \(K_5 \not\subseteq [W]_g\), we obtain \([W]_r = C_4 \cup C_5\) by Lemma 1. Moreover, \(q_r(w,U) = 2\) for every \(w \in W\). Let \(W_1 = \{w_1,w_2,w_3,w_4\}\) and \(W_2 = \{ w_5, w_6, w_7, w_8, w_9 \}\) be the vertex sets of the red \(C_4\) and the red \(C_5\) in \([W]\), where \(w_i w_{i+1}\) for \(i = 1, 2,3,5,6,7, 8\), \(w_4w_1\) and \(w_9w_5\) are red. We may assume that \(w_1u_1\) and \(w_1u_2\) are red and use that \(pr(w,w',U)\) holds for any two vertices \(w,w' \in W_2\) joined green.
First let \(|N_r(w_1) \cap N_r(w) \cap U| = 0\) for every \(w \in W_2\). Thus, \(N_r(w) \cap U \subseteq \{u_3,u_4,u_5\}\) for every \(w \in W_2\). We may assume that \(w_5u_3\) and \(w_5u_4\) are red. From \(pr(w_5,w,U)\) for \(w \in \{w_7,w_8\}\) we derive \(N_r(w) \cap U = \{u_3,u_4\}\) for \(w \in \{w_7,w_8\}\). Now apply \(pr(w_6,w_8,U)\) and \(pr(w_7,w_9,U)\). Hence, also \(N_r(w) \cap U = \{u_3,u_4\}\) for \(w \in \{w_6,w_9\}\). It follows that \(d_r(u_3)\ge 5\), contradicting \(\Delta_r \le 4\).
The remaining case is that \(|N_r(w_1) \cap N_r(w) \cap U| = 2\) for some \(w \in W_2\), say \(w = w_5\). Then \(\{w_1,w_5,u_3,u_4,u_5\}\) induces a green \(K_5\). Consequently, \(K_6-3K_2 \not\subseteq [V]_g\) implies \(q_r(w,\{u_3, u_4, u_5\}) = 2\) for every \(w \in \{w_3,w_7,w_8\}\) and \(q_r(w,\{u_3,u_4,u_5\}) \ge 1\) for \(w\in \{ w_6,w_9\}\). Because of \(pr(w_1,w,U)\) for \(w\in \{ w_6,w_9\}\), we obtain \(q_r(w,\{u_3,u_4, u_5\}) = 2\) also for \(w \in \{ w_6,w_9\}\). Moreover, we may assume that \(w_3u_3\) and \(w_3u_4\) are red. Note that \(pr(w_3,w,U)\) holds for every \(w \in \{w_6,w_7,w_8,w_9\}\). Thus, \(N_r(w) \cap U = \{u_3,u_4\}\) for every \(w \in \{w_6,w_7,w_8,w_9\}\). This implies \(d_r(u_3) \ge 5\) contradicting \(\Delta_r \le 4\).
Case 2. \(K_5-e \subseteq [V]_g\) and \(K_5 \not\subseteq [V]_g\). Let \(U = \{u_1,u_2,u_3,u_4,u_5\}\) be the vertex set of a \(K_5-e \subseteq [V]_g\). We may assume that \(u_1u_5\) is red. If a vertex \(w \in W = V \setminus U\) exists such that \(q_r(w,U) \le 1\), then we either find a green \(K_6-3K_2\) or a green \(K_5\), both a contradiction. Thus, \(q_r(w,U) \ge 2\) for every \(w \in W\). Note that \(\Delta_r \le 4\) and \(K_5 \not\subseteq [V]_g\). Hence, \([W]_r =C_4 \cup C_5\) by Lemma 1. Again let \(W_1 = \{w_1,w_2,w_3,w_4\}\) and \(W_2 = \{ w_5, w_6, w_7, w_8, w_9 \}\) be the vertex sets of the red \(C_4\) and the red \(C_5\) in \([W]\), where \(w_i w_{i+1}\) for \(i = 1, 2,3,5,6,7, 8\), \(w_4w_1\) and \(w_9w_5\) are red. From \(\Delta_r \le 4\) we obtain that \(u_1\) must have a green neighbor in \(W_2\), say \(w_5\). Now consider the two green copies of \(K_5-e\) induced by \(W_3= \{w_1,w_3,w_5,w_6,w_8\}\) and \(W_4 = \{w_2,w_4,w_5,w_7,w_9\}\). Mind that \(W_3 \cap W_4 = \{w_5\}\). If \(q_r(u_1,W_3) \le 1\) or \(q_r(u_1,W_4) \le 1\), then a green \(K_6-3K_2\) or a green \(K_5\) would occur in \([W_3\cup \{u_1\}]\) or \([W_4\cup \{u_1\}]\). Otherwise \(d_r(u_1) \ge 5\), contradicting \(\Delta_r \le 4\).
Case 3.\(K_5-2K_2 \subseteq [V]_g\) and \(K_5 -e\not\subseteq [V]_g\). Let \(U = \{u_1,u_2,u_3,u_4,u_5\}\) be the vertex set of a \(K_5-2K_2 \subseteq [V]_g\). We may assume that \(u_1u_5\) and \(u_2u_4\) are red. If a vertex \(w \in W = V \setminus U\) exists such that \(q_r(w,U) \le 1\) we either find a green \(K_6-3K_2\) or a green \(K_5-e\), a contradiction. Thus, \(q_r(w,U) \ge 2\) for every \(w \in W\). Note that \(\Delta_r \le 4\). Hence, \([W]_r =K_1 \cup 2C_4\) or \([W]_r =C_4 \cup C_5\) by Lemma 1. But then \(K_5-e \subseteq [W]_g \subseteq [V]_g\), a contradiction.
◻
Lemma 2.7. Let \(n \ge 2\). Then \[r(S_{n+2},K_6-3K_2) \le r(S_n,K_6-3K_2) + 5.\]
Proof. Let \(m = r(S_n,K_6-3K_2) + 5\). By (1), \(r(S_n,K_6-3K_2) \ge 2n\), and this implies \(m \ge 2n+5\). Assume that an \((S_{n+2},K_6-3K_2)\)-coloring of \(K_m\) exists. Since \(r(S_n,W_4) = 2n+1\) if \(n\) is even and \(r(S_n,W_4) = 2n-1\) if \(n\) is odd (see [3]) we obtain \(r(S_{n+2},W_4) \le 2n+5 \le m\). Thus, \(S_{n+2} \not\subseteq [V]_r\) forces \(W_4 \subseteq [V]_g\). Let \(U = \{u_1,u_2,u_3,u_4,u_5\}\) be the vertex set of a green \(W_4 = K_5-2K_2\) and \(W = V \setminus U\). Note that \(|W| = r(S_n,K_6-3K_2)\). Hence, \(S_n \subseteq [W]_r\) and a vertex \(w^* \in W\) exists with degree at least \(n-1\) in \([W]_r\). From \(S_{n+2} \not\subseteq [V]_r\) it follows that \(q_r(w^*,U) \le 1\), i.e. \(q_g(w^*,U) \ge 4\).
If \([U]_g = K_5\), then \(K_6-3K_2\subseteq [\{w^*\} \cup U]_g\), a contradiction, and we may assume that \(K_5 \not\subseteq [V]_g\). Now let \([U]_g = K_5-e\) assuming that the edge \(u_1u_5\) is red. If \(w^*\) is joined green to \(u_1\) and \(u_5\), then a green \(K_6-3K_2\) is contained in \([\{w^*\} \cup U]\). Otherwise \(w^*\) is joined red to \(u_1\) or to \(u_5\), say to \(u_1\), but this implies that \([\{w^*\} \cup \{u_2,u_3,u_4,u_5\}]\) is a green \(K_5\). Again we have obtained a contradiction and we may assume that \(K_5-e\not\subseteq [V]_g\). It remains that \([U]_g = K_5-2K_2\). Here we may assume that the edges \(u_1u_2\) and \(u_4u_5\) are red. If \(w^*\) is joined red to \(u_3\), then a green \(K_6-3K_2\) is contained in \([\{w^*\} \cup U]\). Otherwise \(w^*\) is joined green to \(u_3\) and to at least three vertices in \(\{u_1,u_2,u_4,u_5\}\), say to \(u_1\), \(u_2\) and \(u_4\). But this gives a forbidden green \(K_5-e\) in \([\{w^*\} \cup \{u_1,u_2,u_3,u_4\}]\), and we are done. ◻
Now we will use the results obtained in Theorem 2.1 and Lemmas 2.5, 2.6 and 2.7 to prove Theorem 2.3.
At first we will show that the given values are lower bounds for \(r(S_n,K_6-3K_2)\). The exact results of \(r(S_n,C_4)\) for \(n \le 10\) can be found in [1], namely \[\begin{array}{c|ccccccccc} n&\,2\,&\,3\,&\,4\,&\,5\,&\,6\,&\,7\,&8&9&10\\ \hline r(S_n,C_4)&4&4&6&7&8&9&11&12&13 \end{array}\,.\] Applying Theorem 2.1, we obtain the desired lower bounds. It remains to establish the given values as upper bounds for \(r(S_n,K_6-3K_2)\). Obviously, \(r(S_n,K_6-3K_2)\le 6\) for \(2 \le n \le 3\). The other cases are settled by Lemmas 2.5, 2.6 and 2.7.
From Lemma 2.7 and the exact results for \(5 \le n \le 6\) in Theorem 2 we obtain a general upper bound for \(r(S_n,K_6-3K_2)\).
Theorem 2.8. Let \(n \ge 5\). Then \[r(S_n,K_6-3K_2)\le \left\lfloor \frac{5n-2}{2}\right\rfloor.\]
Proof. For \(5 \le n \le 6\) the upper bound matches the exact values in Theorem 2. For \(n \ge 7\), induction on \(n\) using Lemma 2.7, separately for \(n\) even and \(n\) odd, yields the desired upper bound. ◻