title: Gallai-Ramsey numbers for graphs with five vertices and eight edges
authors: Xueli Su Yan Liu
text: 
  
  
  
  
  Gallai-Ramsey numbers for graphs with five vertices and eight edges
  
      Xueli Su, Yan Liu
  
  School of Mathematical Sciences, South China Normal University,
  
   Guangzhou, 510631, P.R. China  This work is supported
  by the Scientific research fund of the Science and Technology Program of Guangzhou, China(No.202002030183), by the Natural Science Foundation of Qinghai, China (No.2020-ZJ-924).
   Correspondence should be addressed to Yan
  Liu(e-mail:liuyan@scnu.edu.cn)
      
  ==========================================================================================================================================================================================================================================================================================================================================================================================================
  
  
  
  
  
  
  A Gallai k-coloring is a k-edge coloring of a complete graph in which
  there are no rainbow triangles. For given graphs G_1, G_2, G_3
  and nonnegative integers r, s, t with that k=r+s+t, the
  k-colored Gallai-Ramsey number gr_k(K_3: r· G_1, 
  s· G_2,  t· G_3) is the minimum integer n such that every Gallai
  k-colored K_n contains a monochromatic copy of G_1 colored
  by one of the first r colors or a monochromatic copy of G_2
  colored by one of the middle s colors or a monochromatic copy of G_3
  colored by one of the last t colors. In this paper, we
  determine the value of Gallai-Ramsey number in the case that
  G_1=B_3^+, G_2=S_3^+ and G_3=K_3. Then the Gallai-Ramsey number
  gr_k(K_3: B_3^+) is obtained. Thus the Gllai-Ramsey numbers for graphs with five vertices and eight edges are solved completely.
  Furthermore, the the Gallai-Ramsey numbers gr_k(K_3: r· B_3^+, 
  (k-r)· S_3^+), gr_k(K_3: r· B_3^+, 
  (k-r)· K_3) and gr_k(K_3: s· S_3^+, 
  (k-s)· K_3) are obtained, respecticely.
  
  
  Key words: Gallai coloring, rainbow triangle, monochromatic graph, Gallai-Ramsey number.
  
  
  
  
  
  
  
  
  
  § INTRODUCTION
  
  
  All graphs considered in this paper are finite, simple and undirected. For a graph G, we use |G| to denote the number of vertices of G, say the order of G.
  The complete graph of order n is denoted by K_n.
  For a subset S⊆ V(G), let G[S] be the subgraph of G induced by S.
  For two disjoint subsets A and B of V(G), E_G(A, B)={ab∈ E(G)  |  a∈ A, b∈ B}. Let G_1=(V_1,E_1) and G_2=(V_2,E_2) be two graphs. The union of G_1 and G_2, denoted by G_1+G_2, is the graph with the vertex set V_1⋃ V_2 and the edge set E_1⋃ E_2. The join of G_1 and G_2, denoted by G_1∨ G_2, is the graph obtained from G_1+G_2 by adding all edges joining each vertex of G_1 and each vertex of G_2.
  For any positive integer k, we write [k] for the set {1, 2, ⋯, k}.
  An edge coloring of a graph is called monochromatic if all edges are colored by the same color. An edge-colored graph is called rainbow if no two edges are colored by the same color.
  
  Given graphs H_1 and H_2, the classical Ramsey number R(H_1, H_2) is the smallest integer n such that for any 2-edge coloring of K_n with red and blue, there exists a red copy of H_1 or a blue copy of H_2.
  Given graphs H_1, H_2, ⋯, H_k, the multicolor Ramsey number R(H_1, H_2, ⋯, H_k) is the smallest positive integer n such that for every k-edge colored K_n with the color set [k], there exists some i∈ [k] such that K_n contains a monochromatic copy of H_i colored by i.
  The multicolor Ramsey number is an obvious generalization of the classical Ramsey number.
  When H=H_1=⋯=H_k, we simply denote R(H_1, ⋯, H_k) by R_k(H). 
  
  In this paper, we study Ramsey number in Gallai-coloring.
  A Gallai-coloring is an edge coloring of a complete graph without rainbow triangle.
  Gallai-coloring naturally arises in several areas including: information theory <cit.>; the study of partially ordered sets, as in Gallai's original paper <cit.> (his result was restated in <cit.> in the terminology of graphs); and the study of perfect graphs <cit.>. 
  A Gallai k-coloring is a Gallai-coloring that uses k colors.
  Given a positive integer k and graphs H_1, H_2, ⋯, H_k, the Gallai-Ramsey number gr_k(K_3: H_1, H_2, ⋯, H_k) is the smallest integer n such that every Gallai k-colored K_n contains a monochromatic copy of H_i in color i for some i∈ [k].
  Clearly, gr_k(K_3: H_1, H_2, ⋯, H_k)≤ R(H_1, H_2, ⋯, H_k) for any k and gr_2(K_3: H_1, H_2)=R(H_1, H_2).
  When H=H_1=⋯=H_k, we simply denote gr_k(K_3: H_1, H_2, ⋯, H_k) by gr_k(K_3: H).
  When H=H_1=⋯=H_s (0≤ s≤ k) and G=H_s+1=⋯=H_k, we use the following shorthand notation 
      gr_k(K_3:s· H, (k-s)· G)=gr_k(K_3:H, ⋯, H_s  times, G, ⋯, G_(k-s)  times).
  
  For nonnegative integers r, s, t, when G_1=H_1=⋯=H_r, G_2=H_r+1=⋯=H_r+s,  and G_3=H_r+s+1=⋯=H_r+s+t with that k=r+s+t, we use the following shorthand notation 
      gr_k(K_3:r· G_1, s· G_2, t· G_3)=gr_k(K_3:G_1, ⋯, G_1_r  times, G_2, ⋯, G_2_s  times, G_3, ⋯, G_3_t  times).
  
  
  The Gallai-Ramsey numbers gr_k(K_3: H) for all the graphs H on five vertices and at most seven edges are obtained (see <cit.>).
  There are two graphs on five vertices and eight edges, one of which is a wheel graph W_4, and the other is a graph B_3^+ obtained from the book graph B_3 by adding an edge between two vertices with degree two. Song <cit.> and Mao <cit.> obtained the Gallai-Ramsey number gr_k(K_3: W_4).
  In this paper, we determine the Gallai-Ramsey number gr_k(K_3: B_3^+).
  In order to get gr_k(K_3: B_3^+), we actually investigate the Gallai-Ramsey number gr_k(K_3:r· B_3^+, s· S_3^+, t· K_3), where S_3^+ denotes the graph obtained from the star S_3=K_1∨K_3 by adding an edge between two pendant vertices, stated in Theorem <ref>.
  
  
  
  
  For nonnegative integers r, s, t, let k=r+s+t. Then
  
      gr_k(K_3:r· B_3^+, s· S_3^+, t· K_3)=
      17^r/2· 5^t/2+1,    if r, t are even, (c_1)
      
      2·17^r/2· 5^t-1/2+1,    if r is even, t is odd, (c_2)
      
      8·17^r-1/2· 5^t-1/2+1,    if r, t are odd, (c_3)
      
      4·17^r-1/2· 5^t/2+1,    if r is odd, t is even, (c_4)
      
      6·17^r/2· 5^s+t-2/2+1,    if r is even and s+t is even, (c_5)
      
      3·17^r/2· 5^s+t-1/2+1,    if r is even and s+t is odd, (c_6)
      
      48· 17^r-1/2· 5^s+t-3/2+1,    if r is odd and t≥1 and s+t is odd, (c_7)
      
      48· 17^r-1/2· 5^s-3/2+1,    if r, s are odd and s≥3 and t=0, (c_8)
      
      9·17^r-1/2+1,    if r is odd and s=1 and t=0, (c_9)
      
      24· 17^r-1/2· 5^s+t-2/2+1,    if r is odd and s+t is even, (c_10)
  
  where s=0 for Condition c_1 to Condition c_4 and s≥1 for Condition c_5 to Condition c_10.
  
  
  
  When we set that s=t=0, r=s=0, r=t=0, respectively, we can get the following Theorem <ref> to Theorem <ref>, respectively. 
  
  
  For any integer r≥1, 
      gr_r(K_3: B_3^+)= 
      17^r/2+1,     if r is even,
      
      4 · 17^(r - 1)/2+1,     if r is odd.
  
  
  
  
  <cit.>
  For a positive integer t,
  
      gr_t(K_3:K_3)=
      5^t/2+1,    if t is even,
      
      2· 5^t-1/2+1,    if t is odd.
  
  
  
  <cit.>
  For a positive integer s,
  
      gr_s(K_3:S_3^+)=
      6·5^s-2/2+1,    if s is even,
      
      3· 5^s-1/2+1,    if s is odd.
  
  
  
  When we set r=0, s=0 and t=0, respectively, we can get the Gallai-Ramsey numbers gr_k(K_3: s· S_3^+, 
  (k-s)· K_3), gr_k(K_3: r· B_3^+, 
  (k-r)· K_3) and gr_k(K_3: r· B_3^+, 
  (k-r)· S_3^+), respectively, which are omitted.
  
  To prove Theorem <ref>, the following theorem is useful.
  
  
  <cit.> (Gallai-partition)
  For any Gallai-coloring of a complete graph G, there exists a partition of V(G) into at least two parts such that there are at most two colors on the edges between the parts and there is only one color on the edges between each pair of parts. The partition is called a Gallai-partition.
  
  
  
  
  
  
  
  
  
  
  
  
  
  § PROOF OF THEOREM <REF>
  
  First, recall some known classical Ramsey numbers which are useful.
  
  <cit.>
  
      R_2(K_3)=6, R_2(S_3^+)=7, R_2(B_3^+)=18, R(K_3, S_3^+)=7, R(K_3, B_3^+)=9, R(S_3^+, B_3^+)=10.
  
  
  
  A sharpness example of the Ramsey number R(H_1, H_2), denoted by C_(H_1, H_2), is a 2-edge colored K_R(H_1, H_2)-1 with red and blue such that there is neither red copy of H_1 nor blue copy of H_2.
  For example, C_(K_3, K_3) is a 2-edge colored K_5 with red and blue such that there is neither red nor blue copy of K_3 and C_(K_3, S_3^+) is a 2-edge colored K_6 with red and blue such that there is neither red copy of K_3 nor blue copy of S_3^+.
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  For the sake of notation, let f(r, s, t)= gr_k(K_3:r· B_3^+, s· S_3^+, t· K_3)-1,  claimed in Theorem <ref>.
  It is easy to check the following inequalities:
  
      f(r, s, t-1)/f(r, s, t)≤1/2,
  
  
      f(r, s-1, t)/f(r, s, t)≤1/2,
  
  
      f(r-1, s, t)/f(r, s, t)≤1/3,    if s=1 and t=0,
      5/16,    others,
  
  
      f(r-1, s+1, t)/f(r, s, t)≤3/4,
  
  
      f(r-1, s, t+1)/f(r, s, t)≤2/3,
  
  
      f(r, s, t-2)/f(r, s, t)≤1/5,
  
  
      f(r, s-1, t-1)/f(r, s, t)≤1/5,
  
  
      f(r, s-2, t)/f(r, s, t)≤1/5,
  
  
      f(r-1, s, t-1)/f(r, s, t)≤1/8,
  
  
      f(r-1, s-1, t)/f(r, s, t)≤1/8,
  
  
      f(r-1, s+1, t-1)/f(r, s, t)≤3/8,
  
  
      f(r-1, s-1, t+1)/f(r, s, t)≤5/16,
  
  
      f(r-2, s+1, t+1)/f(r, s, t)≤15/34,
  
  
      f(r-2, s+1, t)/f(r, s, t)≤3/17,
  
  
      f(r-2, s, t+2)/f(r, s, t)≤16/51,
  
  
      f(r-2, s, t+1)/f(r, s, t)≤8/51,
  
  
      f(r-2, s, t)/f(r, s, t)=1/17 .
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  Now we prove Theorem <ref>.
  
  
  We first prove that gr_k(K_3:r· B_3^+, s· S_3^+, t· K_3)≥ f(r, s, t)+1 by constructing a Gallai k-colored complete graph G_k with order f(r, s, t) which contains no monochromatic copy of B_3^+ colored by one of the first r colors and no monochromatic copy of S_3^+ colored by one of the middle s colors and no monochromatic copy of K_3 colored by one of the remaining t colors.
  For this construction, we use the sharpness example of classical Ramsey results.
  Let Q_1=C_(K_3, K_3), Q_2=C_(K_3, S_3^+), Q_3=C_(K_3, B_3^+), Q_4=C_(S_3^+, S_3^+), Q_5=C_(S_3^+, B_3^+) and Q_6=C_(B_3^+, B_3^+).
  We construct our sharpness example G_k by taking blow-ups of these sharpness examples Q_j  (j∈ [6]).
  A blow-up of a 2-edge-colored graph Q_j with two new colors on an i-edge-colored graph G_i is a new graph G_i+2 obtained from Q_j by replacing each vertex of Q_j with G_i and replacing each edge e of Q_j with a monochromatic complete bipartite graph (V(G_i), V(G_i)) in the same color with e.
  By induction on i, 
  suppose that we have constructed graphs G_i, where G_i is i-edge-colored such that G_i contains no rainbow triangle and no appropriately colored monochromatic B_3^+ or S_3^+ or K_3.
  If i=k, then the construction is completed.
  Otherwise, we construct G_i+2 by taking a blow-up of 2-edge-colored Q_j with two new colors on G_i by distinguishing the following cases. 
  
  Case a. If the two new colors are in the first r colors, then we construct G_i+2 by making a blow-up of Q_6 on G_i. 
  
  Case b. If the two new colors are in the middle s colors, then we construct G_i+2 by making a blow-up of Q_1 on G_i where i≥1. 
  
  Case c. If the two new colors are in the last t colors, then we construct G_i+2 by making a blow-up of Q_1 on G_i.
  
  
  
  
  
  
  
  
  
  
  The base graphs (i.e., the first graphs in the induction) for this construction are constructed as follows.
  
  For Condition c_1, the base graph G_0 is a single vertex.
  
  For Condition c_2, the base graph G_1 is a K_2 colored by one of the last t colors.
  
  For Condition c_3, the base graph G_2 is a Q_3 colored by two colors in which one is in the first r colors and the other is in the last t colors.
  
  For Condition c_4, the base graph G_1 is a monochromatic K_4 colored by one of the first r colors.
  
  For Condition c_5, the base graph G_2 is a Q_4 colored by two colors which are in the middle s colors if s, t are both even and the base graph G_2 is a Q_2 colored by two colors in which one is in the middle s colors and the other is in the last t colors if s, t are both odd.
  
  For Condition c_6, if s is odd and t is even, the base graph G_1 is a monochromatic copy of K_3 colored by one of the middle s colors.
  If s is even and t is odd, the base graph G_3 is a blow-up of Q_1 on a monochromatic K_3, where K_3 is colored by one of the middle s colors and Q_1 is colored by two new colors one of which is in the middle s colors and the other is in the last t colors.
  
  For Condition c_7, if s is even and t is odd, the base graph G_4 is a blow-up of Q_3 on Q_4, where Q_4 is colored by two colors which are in the middle s colors and Q_3 is colored by two colors one of which is in the first r colors and the other is in the last t colors .
  If s is odd and t is even, then we first construct G_3. G_3 is a blow-up of Q_3 on a monochromatic K_3, where K_3 is colored by one of middle s colors and Q_3 is colored by two colors one of which is in the first r colors and the other is in the last t colors. The base graph G_4 is a blow-up of a monochromatic K_2 on G_3, where K_2 is colored by a new color in the last t colors.
  
  For Condition c_8, the base graph G_4 is a blow-up of Q_3 on Q_4, where Q_4 is colored by two colors which are in the middle s colors and Q_3 is colored by two new colors one of which is in the first r colors and the other is in the middle s colors.
  
  For Condition c_9, the base graph G_2 is a Q_5 with two colors in which one is in the first r colors and the other is in the middle s colors.
  
  For Condition c_10, if s and t are both odd, the base graph G_3 is a blow-up of Q_3 on a monochromatic K_3, where K_3 is colored by one of the middle s colors and Q_3 is colored by two colors one of which is in the first r colors and the other is in the last t colors.
  If s and t are even, the base graph G_3 is a blow-up of Q_3 on a monochromatic K_3, where K_3 is colored by one of the middle s colors and Q_3 is colored by two new colors one of which is in the first r colors and the other is in the middle s colors.
  
  Now we only check G_k constructed by the method as above under the two conditions c_1 and c_5, others can be checked similarly, omitted. 
  
  Condition c_1. r, t are even and s=0. Then k=r+t. First the basic graph is G_0=K_1. Next by Case a, we can construct G_r of order 17^r/2. Finally, by Case c, we continue to construct G_r+2, G_r+4, …, G_r+t. So we can get that |G_k|=17^r/2·5^t/2=f(r, s, t) and G_k is a Gallai k-colored complete graph which contains neither monochromatic copy of B_3^+ colored by one of the first r colors nor monochromatic copy of K_3 colored by one of the remaining t colors.
  
  Condition c_5. If r is even and s, t are old, then we first have the basic graph G_2=K_6. Next by Case a, we can construct G_r+2 of order 6·17^r/2. Then by Case b, we continue to construct G_r+s+1 of order 6·17^r/2·5^s-1/2. Finally, by Case c, we continue to construct G_r+s+3, G_r+s+5, …, G_r+s+t. So we can get that |G_k|=6·17^r/2·5^s+t-2/2=f(r, s, t) and G_k is a Gallai k-colored complete graph which contains no appropriately colored monochromatic B_3^+ or S_3^+ or K_3.
  Similarly, we can get that |G_k|=f(r, s, t) if r is even and s, t are even.
  
  Therefore, gr_k(K_3:r· B_3^+, s·
  S_3^+, t· K_3)≥ f(r, s, t)+1.
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  Now we prove that gr_k(K_3:r· B_3^+, s·
  S_3^+, t· K_3)≤ f(r, s, t)+1 by induction on 3r+2s+t.
  The statement holds in the case that 3r+2s+t≤ 2 or k≤2 by Lemma <ref>.
  So we can assume that k≥3, 3r+2s+t≥3, and the statement holds for any r^', s^' and t^' such that 3r^'+2s^'+t^'<3r+2s+t.
  Let n=f(r, s, t)+1 and G be a Gallai k-colored complete graph of order n.
  Then n=f(r, s, t)+1≥ f(0, 0, 3)+1=11.
  Suppose, to the contrary, that G contains neither monochromatic copy of B_3^+ in any one of the first r colors nor monochromatic copy of S_3^+ in any one of the middle s colors nor monochromatic copy of K_3 in any one of the last t colors.
  By Theorem <ref>, there exists a Gallai-partition of V(G). Choose a Gallai-partition with the smallest number of parts, say (V_1, V_2, ⋯, V_q) and let each part H_i=G[V_i] for i∈ [q].
  Then q≥ 2.
  
  
  
  We first consider the case that q=2. W.L.O.G, suppose that the color on the edges between two parts is red.
  First suppose that red is in the last t colors or in the middle s colors.
  Then H_1 and H_2 both have no red edges, otherwise, there exists a red K_3 or a red S_3^+, a contradiction.
  Hence by the induction hypothesis, |H_i|≤ f(r, s, t-1) if red is in the last t colors and |H_i|≤ f(r, s-1, t) red is in the middle s colors for each i∈ [2].
  By Inequalities (<ref>) and (<ref>), we have that 
      |G|=|H_1|+|H_2|≤ 2×1/2f(r, s, t)<n,
   a contradiction.
  Next suppose that red is in the first r colors.
  If both H_1 and H_2 have a red edge, then G has a red B_3^+, a contradiction.
  First suppose that H_1 and H_2 both have no red edges.
  By the induction hypothesis and Inequality (<ref>),
  
      |G|=|H_1|+|H_2|≤ 2f(r-1, s, t)≤2/3 f(r, s, t)<n,
   a contradiction.
  Then suppose that H_1 has a red edge, but H_2 has no red edges.
  Clearly, H_1 contains no red S_3^+, otherwise, G contains a red B_3^+, a contradiction.
  We first consider the case that H_1 contains a red K_3. To avoid a red B_3^+, we have that |H_2|=1.
  Then H_1 can be considered that red is moved in the middle s colors.
  By the induction hypothesis and Inequality (<ref>), we get that
  
      |G|=|H_1|+|H_2|≤ f(r-1, s+1, t)+1≤3/4 f(r, s, t)+1<n,
   a contradiction.
  So we can assume that H_1 contains no red K_3.
  Thus H_1 can be considered that red is moved in the last t colors.
  By the induction hypothesis and Inequalities (<ref>) and (<ref>), we get that
  
      |G|=|H_1|+|H_2|≤ f(r-1, s, t+1)+f(r-1, s, t)≤(2/3+1/3) f(r, s, t)<n,
   a contradiction.
  
  Now we can assume that q≥ 3 and the two colors appeared in the Gallai-partition (V_1, V_2, ⋯, V_q) are red and blue.
  If there exists one part (say V_1) such that all edges joining V_1 to the other parts are colored by the same color, then we can find a new Gallai-partition with two parts (V_1, V_2⋃⋯⋃ V_q), which contradicts with that q is smallest.
  It follows that q≠ 3 and the following fact holds.
  
  
  For each part V_i, there exist both red and blue edges connecting V_i and the other parts.
  
  
  Now we can assume that q≥ 4.
  First suppose that red or blue are in the middle s colors. Then we have the following
  facts.
  
   If red is in the middle s colors, then G contains no red K_3 and the statement holds for blue symmetrically.
  
  
  Otherwise, suppose that there is a red K_3=v_1 v_2 v_3 in G.
  Let U be the union of parts V_j containing a vertex in {v_1, v_2, v_3}.
  Then U contains at most 3 parts of Gallai-partition in G.
  If there exists a red edge in E_G(U, V(G)∖ U), then G contains a red S_3^+, a contradiction.
  It follows that all edges in E_G(U, V(G)∖ U) are blue.
  Then (U, V(G)∖ U) is a new Gallai-partition which contradicts with that q≥4 and q is smallest.
  
  By Fact <ref> and Fact <ref>, we have the following Fact.
  
  If red is in the middle s colors, then every H_i has no red edges and the statement holds
  for blue symmetrically.
  
  
  
  Now we consider the following cases.
  
  
  Neither red nor blue is in the first r colors.
  
  
  First we prove the following claim.
  
  G contains neither red K_3 nor blue K_3.
  
  
  
  If red and blue are both in the last t colors, the statement holds clearly.
  Next suppose that both red and blue are within the middle s colors. By Fact <ref>, the statement holds. Finally, suppose that red appears in the middle s colors, blue appears in the last t colors, W.L.O.G..
  Then G has no blue K_3.
  By Fact <ref>, we have that G contains no red K_3.
  Complete the proof of Claim <ref>.
  
  
  Since R_2(K_3)=6, we have q≤5 by Claim <ref>.
  By Fact <ref> and Claim <ref>, each H_i contains neither red nor blue edges.
  By the induction hypothesis, for each H_i, we have that
  
      |H_i|≤
      f(r, s, t-2), if red and blue are both in the last t colors,
      
      f(r, s-2, t), if red and blue are both in the middle s colors,
      
      f(r, s-1, t-1), if red is in the middle s colors and blue in the last t colors.
  
  By Inequalities (<ref>)-(<ref>), we have that
  
      |G|=∑_i=1^q|H_i| ≤ 5×1/5f(r, s, t) < n,
  
  a contradiction.
  The proof of Case <ref> is completed.
  
  Now we consider the case that red or blue are in the first r colors, we have the following fact and claim.
  
  
  If red is in the first r colors and both H_i and H_j contain red edges, then the edges in E_G(V_i, V_j) must be blue and the statement holds for blue symmetrically.
  
  
  Otherwise, suppose that the edges in E_G(V_i, V_j) are red.
  To avoid a red B_3^+, all edges in E_G({V_i, V_j}, V(G)∖{V_i, V_j}) are blue.
  Then (V_i∪ V_j, V(G)∖(V_i∪ V_j)) is a new Gallai-partition which contradicts with that q≥4 and q is smallest.
  
  
  
  
  
  
  
  
  
  
  
  Let red be in the first r colors and X is the union of p parts of the Gallai-partition such that G[X] contains neither red B_3^+ nor blue edges. Then 
  
  (i) |X|≤ f(r-1, s, t)+f(r-1, s, t-1) if blue is in the last t colors.
  
  (ii) |X|≤ f(r-1, s-1, t+1)+f(r-1, s-1, t) if blue is in the middle s colors.
  
  (iii) |X|≤ f(r-2, s, t+1)+f(r-2, s, t) if blue is in the first r colors.
  
  
  
  Since G[X] contains no blue edges, every pair of parts in G[X] are joined by red edges.
  Since G[X] has no red B_3^+, we have that p≤ 4.
  By Fact <ref>, there is at most one part in G[X] containing red edges.
  Then we distinguish two cases.
  
  Case I. Each part in G[X] has no red edges.
  
  If p≤ 3, then 
      |X|≤
      3f(r-1, s, t-1), if blue is in the last t colors,
      
      3f(r-1, s-1, t), if blue is in the middle s colors,
      
      3f(r-2, s, t), if blue is in the first r colors.
  
  By the definition of f(r, s, t), we can check that 3f(r-1, s, t-1)≤ f(r-1, s, t)+f(r-1, s, t-1), 3f(r-1, s-1, t)≤ f(r-1, s-1, t+1)+f(r-1, s-1, t) and 3f(r-2, s, t)≤ f(r-2, s, t+1)+f(r-2, s, t). The statement of Claim <ref> holds in this case.
  If p=4, to avoid a red B_3^+, then we have that |X|=4.
  Clearly, the statement still holds.
  
  Case II. There is a unique part contains a red edge in G[X], say H_1.
  
  If H_1 contains a red K_3, then to avoid a red B_3^+, |X\ V_1|≤ 1.
  So 
      |X|≤ |H_1|+1≤
      f(r-1, s+1, t-1)+1, if blue is in the last t colors,
      
      f(r-1, s, t)+1, if blue is in the middle s colors,
      
      f(r-2, s+1, t)+1, if blue is in the first r colors.
  
  In this case, the statement of Claim <ref> holds.
  If H_1 contains no red K_3, then 
      |H_1|≤
      f(r-1, s, t), if blue is in the last t colors,
      
      f(r-1, s-1, t+1), if blue is in the middle s colors,
      
      f(r-2, s, t+1), if blue is in the first r colors.
  
  Since G[X] has no red B_3^+, we have that p≤ 3.
  Furthermore, |X|=|H_1|+2 if p=3 and |X|=|H_1| if p=1. It is easy to check that the statement also holds.
  If p=2, then the other part in G[X], say H_2, contains no red edges.
  So 
      |X|=|H_1|+|H_2|≤
      f(r-1, s, t)+f(r-1, s, t-1), if blue is in the last t colors,
      
      f(r-1, s-1, t+1)+f(r-1, s-1, t), if blue is in the middle s colors,
      
      f(r-2, s, t+1)+f(r-2, s, t), if blue is in the first r colors.
  
  Complete the proof of Claim <ref>.
  
  
  
  For the part V_1 of Gallai-partition, let V_R (V_B) be the union of parts V_i such that the edges in E_G(V_1, V_i) are red (blue) and H_R=G[V_R], H_B=G[V_B].
  
  
  Exactly one of red and blue is in the first r colors. 
  
  
  W.L.O.G., suppose that red appears in the first r colors. Then G has no red B_3^+.
  If blue appears in the last t colors,
  then there is no blue K_3 in G.
  If blue appears in the middle s colors, then by Fact <ref>, we get that there is also no blue K_3 in G.
  Since R(B_3^+, K_3)=9, q≤ 8.
  By Fact <ref>, each H_i contains neither red S_3^+ nor blue edges.
  If each H_i contains no red edges, then by the induction hypothesis and Inequalities (<ref>) and (<ref>), we get that
  
      |G|=∑_i=1^q|H_i|≤
      8 f(r-1, s, t-1) ≤ f(r, s, t) < n, if blue is in the last t colors,
      
      8 f(r-1, s-1, t) ≤ f(r, s, t) < n, if blue is in the middle s colors.
  
  a contradiction.
  It follows that there is at least one part containing red edges.
  W.L.O.G., suppose that H_1 contains a red edge.
  So we consider the following two Subcases.
  
  
  H_1 has a red K_3.
  
  
  To avoid a red B_3^+ or a blue K_3, we get that |H_R|=1 and H_B contains no blue edges.
  By the induction hypothesis and Inequalities (<ref>) and (<ref>), (<ref>) and (<ref>), we get that
  
      |G|
         =   |H_1|+|H_R|+|H_B| 
         ≤   
      f(r-1, s+1, t-1)+1+f(r, s, t-1)≤7/8 f(r, s, t)+1<n, if blue is in the last t colors,
      
      f(r-1, s, t)+1+f(r, s-1, t)≤5/6 f(r, s, t)+1<n, if blue is in the middle s colors.
  
  a contradiction.
  
  
  H_1 has no red K_3.
  
  
  To avoid a blue K_3, H_B contains no blue edges. By Claim <ref>, we have that
  
      |H_B|≤
      f(r-1, s, t)+f(r-1, s, t-1), if blue is in the last t colors,
      
      f(r-1, s-1, t+1)+f(r-1, s-1, t), if blue is in the middle s colors.
  
  To avoid a red B_3^+, H_R contains no red edges if |H_R|≥ 3.
  It follows that the edges between each pair of parts in H_R are blue.
  Since G has no blue K_3, H_R contains at most two parts of Gallai-partition and each part in H_R contains no blue edges. By the induction hypothesis,
  
      |H_R|
      ≤
      2f(r-1, s, t-1), if blue is in the last t colors,
      
      2f(r-1, s-1, t), if blue is in the middle s colors.
  
  If |H_R|≤ 2, then the Inequality (<ref>) still holds.
  By the induction hypothesis and Inequalities (<ref>) and (<ref>), (<ref>) and (<ref>), we get that
  
      |G|
         =   |H_1|+|H_B|+|H_R| 
         ≤   
      2f(r-1, s, t)+3f(r-1, s, t-1)≤ f(r, s, t)<n, if blue is in the last t colors,
      
      2f(r-1, s-1, t+1)+3f(r-1, s-1, t)<n, if blue is in the middle s colors.
  
  a contradiction.
  The proof of Case <ref> is completed.
  
  
  Both red and blue are in the first r colors.
  
  
  In this case, the graph G contains neither red nor blue B_3^+.
  Since R_2(B_3^+)=18, we have q≤17.
  First we prove the following claim.
  
  
  Each part H_i of G contains neither red nor blue K_3.
  
  
  
  To the contrary, suppose that there exist one part, say H_1, containing a red K_3 and a blue K_3.
  To avoid a red or blue B_3^+, we have that |H_R|=|H_B|=1.
  So we get q=3, which contradicts with that q≥4.
  It follows that each part of G at most contains a red or a blue K_3.
  W.L.O.G., suppose that there is a part H_1 containing a blue K_3 but no red K_3.
  To avoid a blue B_3^+, we get that |H_B|=1.
  If H_1 contains no red edges, then to avoid a red B_3^+, H_R contains no red K_3.
  By induction hypothesis and Inequalities (<ref>) and (<ref>), we have that
  
      |G|
      =|H_1|+|H_R|+|H_B| ≤ f(r-2, s+1, t)+f(r-1, s, t+1)+1
      ≤43/51f(r, s, t)+1<n,
  
  a contradiction.
  Now we assume that H_1 contains a red edge. To avoid a red B_3^+, H_R contains no red edges if |H_R|≥ 3. By induction hypothesis, |H_R|≤ f(r-1, s, t). If |H_R|≤ 2, then |H_R|≤ f(r-1, s, t) clearly.
  By Inequalities (<ref>) and (<ref>), we have that
  
      |G|
      =|H_1|+|H_R|+|H_B|
      ≤  f(r-2, s+1, t+1)+ f(r-1, s, t)+1≤79/102f(r, s, t)+1<n,
  
  a contradiction.
  Complete the proof of Claim <ref>.
  
  Now we consider the following subcases.
  
  
  
  
  
  
  
  
  
  
  There exists a part H_1 containing both a red and a blue edge.
  
  
  To avoid a blue or red B_3^+, H_R contains no red edges and H_B contains no blue edges if |H_R|, |H_B|≥ 3. By induction hypothesis, we have that |H_R|, |H_B|≤ f(r-1, s, t).
  If |H_R|, |H_B|≤ 2, then |H_R|, |H_B|≤ f(r-1, s, t) clearly.
  By Inequalities (<ref>) and (<ref>), we have that
  
      |G|
      =|H_1|+|H_R|+|H_B|
      ≤  f(r-2, s, t+2)+ 2f(r-1, s, t)≤50/51f(r, s, t)<n,
  
  a contradiction.
  
  Now we can assume that each part contains no red edges or no blue edges in the following.
  We call a part free if it contains neither red nor blue edges.
  We call a part red (blue) if it contains only red (blue) edges.
  By induction hypothesis and Claim <ref>, we have that |H_i|≤ f(r-2, s, t) if H_i is a free part and |H_i|≤ f(r-2, s, t+1) if H_i is a red or blue part.
  
  
  Each part H_i is a free part.
  
  By Inequality (<ref>), we have that
  
      |G|=
      ∑_i=1^q|H_i| ≤ 17 f(r-2, s, t) =f(r, s, t)<n,
  
  a contradiction.
  
  
  There exists one part H_1 which is a red or blue part.
  
  
  W.L.O.G., suppose that H_1 is a red part.
  If |H_R|≥ 3, then H_R has no red edges since G has no red B_3^+.
  Then by Claim  <ref>, we have that |H_R|≤ f(r-2, s, t)+f(r-2, s, t+1).
  If |H_R|≤ 2, then |H_R|≤ 2≤ f(r-2, s, t)+f(r-2, s, t+1) clearly.
  To avoid a blue B_3^+, H_B contains no blue K_3.
  Since H_B contains neither blue K_3 nor red B_3^+ and R(K_3, B_3^+)=9, we have that H_B contains at most 8 parts of Gallai-partition. First suppose that all parts in H_B are free parts. Then |H_B|≤ 8 f(r-2, s, t).
  By Inequalities (<ref>) and (<ref>), we have that
  
      |G|
      =|H_1|+|H_R|+|H_B| ≤ 2f(r-2, s, t+1)+9f(r-2, s, t)
      ≤35/51f(r, s, t)<n,
  
  a contradiction.
  Next suppose that there is one part, say H_2, such that H_2 (H_2⊆ H_B) is a blue or red part.
  let V_2R (V_2B) be the union of parts H_i such that the edges in E_G(V_2, V_i) are red (blue) and H_2R=G[V_2R], H_2B=G[V_2B].
  If H_2 is a blue part, then to avoid a red or blue B_3^+, H_2R contains neither red nor blue K_3 and H_2B=∅.
  By the induction hypothesis, |H_B|=|H_2|+|H_2R|≤ f(r-2, s, t+1)+ f(r-2, s, t+2).
  By Inequalities (<ref>), (<ref>) and (<ref>), we have that
  
      |G|
         =   |H_1|+|H_R|+|H_B| ≤ 3f(r-2, s, t+1)+f(r-2, s, t)+f(r-2, s, t+2)
         ≤   43/51f(r, s, t)<n,
  
  a contradiction.
  If H_2 is a red part, then H_2B contains no blue edges since G contains no blue B_3^+.
  Then by Claim <ref>, |H_2B|≤ f(r-2, s, t+1)+f(r-2, s, t).
  To avoid a red B_3^+, H_2R contains no red edge if |H_2R|≥ 3.
  It follows that the edges between each pair of parts in H_2R are blue.
  Since G has no blue B_3^+, H_2R contains no blue K_3.
  It follows that there are at most two parts in H_2R.
  If H_2R contains only one part, then H_2R is a free part or a blue part.
  We can get that |H_2R|≤ f(r-2, s, t+1).
  If H_2R contains two parts, then two parts both are free parts.
  We have that |H_2R|≤ 2f(r-2, s, t)≤ f(r-2, s, t+1).
  
  
  
  
  
  
  
  
  
  So 
      |H_B|
      =|H_2|+|H_2R|+|H_2B| ≤ 3f(r-2, s, t+1)+f(r-2, s, t).
  
  By Inequalities (<ref>) and (<ref>), we have that
  
      |G|
      =|H_1|+|H_R|+|H_B| ≤ 5f(r-2, s, t+1)+2f(r-2, s, t)
      ≤46/51f(r, s, t)<n,
  
  a contradiction.
  Complete the proof of Case <ref> and then the proof of Theorem <ref>.
  
  
  
  
  
  
  
  
  