Three color Ramsey numbers for graphs with at most 4 vertices

Three color Ramsey numbers for graphs with at most 4 vertices Luis Boza University of Sevilla Department of Applied Mathematics I Reina Mercedes 2, 41012-Seville, Spain [email protected] Janusz Dybizba´nski Tomasz Dzido University of Gda´nsk Institute of Informatics Wita Stwosza 57, 80-952 Gda´nsk, Poland [email protected], [email protected] Submitted: Mar 23, 2012; Accepted: Dec 8, 2012; Published: Dec 31, 2012 Mathematics Subject Classifications: 05C55, 05D10 Abstract For given graphs H1, H2, H3, the 3-color Ramsey number R(H1, H2, H3) is the smallest integer nsuch that if we arbitrarily color the edges of the complete graph of order nwith 3 colors, then it always contains a monochromatic copy of Hicolored with i, for some 1 ⩽i⩽3. We study the bounds on 3-color Ramsey numbers R(H1, H2, H3), where Hiis an isolate-free graph different from K2with at most four vertices, establishing that R(P4, C4, K4) = 14, R(C4, K3, K4−e) = 17, R(C4, K3+e, K4−e) = 17, R(C4, K4− e, K4−e) = 19, 28 ⩽R(C4, K4−e, K4)⩽36, R(K3, K4−e, K4)⩽41, R(K4−e, K4− e, K4)⩽59 and R(K4−e, K4, K4)⩽113. Also, we prove that R(K3+e, K4−e, K4− e) = R(K3, K4−e, K4−e), R(C4, K3+e, K4)⩽max{R(C4, K3, K4),29}⩽32, R(K3+e, K4−e, K4)⩽max{R(K3, K4−e, K4),33}⩽41 and R(K3+e, K4, K4)⩽ max{R(K3, K4, K4),2R(K3, K3, K4)+2}⩽79. This paper is an extension of the article by Arste, Klamroth, Mengersen [Utilitas Mathematica, 1996]. 1 Introduction In this paper all graphs considered are undirected, finite and contain neither loops nor multiple edges. Let Gbe such a graph. The vertex set of Gis denoted by V(G), the edge set of Gby E(G), and the number of edges in Gby e(G). The degree of the vertex vand the number of the edge incident to vcolored with color iare denoted with d(v) and di(v), respectively. By δi(G) and ∆i(G) we denote the minimum and the maximum degree of vertices in Gthat are colored with color i, respectively. The open neighborhood of vertex vin color iin graph Gis Ni(v) = {u∈V(G)|{u, v} ∈ E(G) and {u, v}is colored with color i}. Define G[S] to be a subgraph of Ginduced by 1 a set of vertices S⊆V(G) and Gito be a graph induced by the edges of Gcolored with color i. Let Pn(resp. Cn) be the path (resp. cycle) on nvertices. The cardinality of a set Ais denoted by |A|. For given graphs G1, G2, . . . , Gk,k⩾2, the multicolor Ramsey number R(G1, G2, . . ., Gk) is the smallest integer nsuch that if we arbitrarily color the edges of the complete graph of order nwith kcolors, then it always contains a monochromatic copy of Gicolored with the color i, for some 1 ⩽i⩽k. A coloring of the edges of n-vertex complete graph with mcolors is called a (G1, G2, . . . , Gm;n)-coloring, if it does not contain a subgraph isomorphic to Gicolored with the color i, for each i. The set of all non-isomorphic (G1, . . . , Gm;n)-colorings is denoted by (G1, . . . , Gm;n). We refer to consecutive colors corresponding to the parameters of colorings as red, blue and green. In this paper we consider isolate-free graphs different from K2with at most four vertices, improving some results from the article by Arste, Klamroth, Mengersen [1] from 1996 and [9]. Note that R(H1, H2, H3) = R(Hσ(1), Hσ(2), Hσ(3)) for every permutation σof {1,2,3}. The case K2is omitted here, because R(K2, H2, H3) = R(H2, H3) and these numbers were already determined in [6, 7, 12]. We use the following two formulas, which are very well known: R(H0 1, H0 2, H0 3)⩾R(H1, H2, H3), if Hiis a subgraph of H0 i. (1) R(H1, H2, H3)⩽R(H1−v1, H2, H3) + R(H1, H2−v2, H3) + R(H1, H2, H3−v3)−1, if vi∈V(Hi), with strict inequality when the right-hand-side and at least one of its terms are even. (2) 2 Results The values R(H1, H2, H3) are known if: •some Hiis P3, 2K2,P4or K1,3, except R(P4, C4, K4) [1, 4, 5, 10, 15, 17], •some Hiis C4,K3,K3+eor K4−eand the other are C4,K3or K3+e, except R(K3, C4, K4−e) and R(K3+e, C4, K4−e) [1, 3, 9, 11, 12, 26, 27]. Also, bounds of other values are known [1, 9, 10, 16, 18, 22, 23, 27, 28]. In this paper we improve the lower bound R(C4, K4−e, K4)⩾27 obtained from (1). Also, we improve the upper bounds R(C4, K3, K4−e)⩽25, R(C4, K3+e, K4−e)⩽25, R(C4, K3+e, K4)⩽43, R(C4, K4−e, K4)⩽54, R(K3, K4−e, K4)⩽44, R(K3+e, K4− e, K4)⩽44, R(K4−e, K4−e, K4)⩽60 and R(K4−e, K4, K4)⩽121, obtained from (2), as well as R(P4, C4, K4)⩽15 [1] and R(C4, K4−e, K4−e)⩽22 [9]. We prove that R(P4, C4, K4) = 14, R(C4, K3, K4−e) = 17, R(C4, K3+e, K4−e) = 17, R(C4, K4−e, K4−e) = 19, 28 ⩽R(C4, K4−e, K4)⩽36, R(K3, K4−e, K4)⩽41, R(K4−e, K4−e, K4)⩽59 and R(K4−e, K4, K4)⩽113. 2 For some classes of Gand H, it was known that R(K3+e, G, H) = R(K3, G, H), for instance R(K3+e, K3+e, K4) = R(K3, K3+e, K4) = R(K3, K3, K4) [1] and R(K3+ e, K3+e, K4−e) = R(K3, K3+e, K4−e) = R(K3, K3, K4−e) [27]. We prove that R(K3+e, K4−e, K4−e) = R(K3, K4−e, K4−e). Also, we prove that R(C4, K3+e, K4)⩽ max{R(C4, K3, K4),29}⩽32, R(K3+e, K4−e, K4)⩽max{R(K3, K4−e, K4),33}⩽41 and R(K3+e, K4, K4)⩽max{R(K3, K4, K4),2R(K3, K3, K4)+2}⩽79. Now, we give the values and bounds of R(H1, H2, H3) in the following tables. Although the first two complete tables and parts of the remaining tables are shown in [1], for the sake of completeness, we repeat them below. In these tables, the lower bounds obtained from (1) are marked with a “*”. Also, we will mark with “†” the upper bounds obtained using (2). We use bold style to denote the new values or bounds presented in this paper. P35[5] 2K24[1] 5[1] P45[1] 5[1] 5[1] K1,35[5] 6[1] 7[1] 7[5] C46[1] 6[1] 7[1] 7[17] 8[1] K35[15] 6[1] 7[1] 9[15] 8[1] 11[4] K3+e5[1] 6[1] 7[1] 9[1] 8[1] 11[1] 11[1] K4−e7[1] 6[1] 7[1] 9[1] 9[1] 11[1] 11[1] 11[10] K47[15] 8[1] 10[1] 13[15] 13[1] 17[4] 17[1] 17[1] 35[4] P3P32K2P4K1,3C4K3K3+e K4−e K4 Table 1: Values of R(P3, H1, H2). 2K26[17] P46[17] 6[17] K1,36[17] 6[17] 7[17] C46[17] 6[17] 7[17] 7[17] K37[17] 8[17] 8[17] 8[15] 8[17] K3+e7[17] 8[17] 8[17] 8[17] 8[17] 8[17] K4−e7[17] 8[17] 8[17] 9[17] 8[17] 8[17] 11[17] K48[17] 11[17] 11[17] 11[17] 11[17] 11[17] 13[17] 20[17] 2K22K2P4K1,3C4K3K3+e K4−e K4 Table 2: Values of R(2K2, H1, H2). 3 P46[14] K1,37[1] 7[1] C47[1] 8[1] 9[1] K39[1] 11[1] 9[1] 16[4] K3+e9[1] 11[1] 9[1] 16[1] 16[1] K4−e10[1] 11[1] 11[1] 16[1] 16[1] 16[1] K413[1] 13[1] 14 25[4] 25[1] 25[1] 52[4] P4P4K1,3C4K3K3+e K4−e K4 Table 3: Values of R(P4, H1, H2). K1,38[5] C48[1] 9[1] K311[15] 11[1] 16[4] K3+e11[1] 11[1] 16[1] 16[1] K4−e11[1] 11[1] 16[1] 16[1] 16[1] K416[15] 16[17] 25[4] 25[1] 25[1] 52[4] K1,3K1,3C4K3K3+e K4−e K4 Table 4: Values of R(K1,3, H1, H2). C411[3] K312[26] 17[11] K3+e12[1] 17[1] 17[1] K4−e16[9] 17 17 19 K420[9]-22[28] 27[9]-32[28] 27∗-32 28-36 52∗-72[28] C4C4K3K3+e K4−e K4 Table 5: Values and bounds of R(C4, H1, H2). K317[12] K3+e17[1] 17[1] K4−e17[27] 17[27] 21[27]-27[27] K430[16]-31[23] R(K3, K3, K4)[1] 30∗-41 55[18]-79† K3K3K3+e K4−e K4 Table 6: Values and bounds of R(K3, H1, H2). 3 Proofs 3.1 R(P4, H1, H2) In [1] it is claimed that 14 ⩽R(P4, C4, K4)⩽15, but no (P4, C4, K4; 13)-coloring is showed. A (P4, C4, K4; 13)-coloring can be found in the Appendix. In this subsection we 4 K3+e17[29] K4−e17[27] R(K3, K4−e, K4−e) K4R(K3, K3, K4)[1] 30∗-41 55∗-79† K3+eK3+e K4−e K4 Table 7: Values and bounds of R(K3+e, H1, H2). K4−e28[10]-30[22] K433[27]-59 55∗-113 K4−eK4−e K4 Table 8: Bounds on R(K4−e, H1, H2). K4128[13]-236† K4K4 Table 9: Bounds on R(K4, K4, K4). will prove that R(P4, C4, K4) = 14. Let Fbe a P4-free graph and let S(F) be the set of (P4, C4, K4;|V(F)|)-colorings of Gsuch that G1=F. We note that R(P4, C4, K4) = 14 if and only if for any P4-free graph Fof order 14 S(F) is empty. Let Hand H0be two P4-free graphs. It is easy to obtain S(H0) from S(H) if one of the following two algorithms is applied: Case a) His an induced subgraph of H0such that |V(H0)|=|V(H)|+ 1. Algorithm 1. Input: coloring G∈S(H). Output: set of all one-vertex extensions of Gwhich are in S(H0). For instance, if we consider the coloring Gbelonging to S(K2∪K1) with 3 vertices, such that the edge {1,2}is red and both {1,3}and {2,3}are blue, then we obtain two colorings of four vertices belonging to S(2K2), adding a new vertex, assigning red color to {3,4}, green color to {1,4}and blue or green color to {2,4}. The coloring such that {1,4}and {2,4}are blue, is not considered because it contains a blue C4. The coloring such that {1,4}is blue and {2,4}is green, is not considered because it is isomorphic to coloring in which {1,4}is green and {2,4}is blue. Case b) H0is a subgraph of Hsuch that |V(H0)|=|V(H)|. Algorithm 2. Input: coloring G∈S(H). Output: set of all colorings of S(H0) obtained assigning blue or green color to some edges of G. For instance, if we consider the coloring Gbelonging to S(2K2∪K1) with 5 vertices, such that the edges {1,2}and {3,4}are red, {1,5}is blue and the remaining seven 5 edges are green, then we obtain three colorings of five vertices belonging to S(K2∪3K1), assigning blue color to {3,4}or assigning blue or green color to {1,2}. The coloring obtained assigning green color to {3,4}is not considered because it contains a green K4. The lists of graphs generated in order to prove that S(F) = ∅for any P4-free graph Fof order 14 are not very large, thus, it is not necessary to utilize the program nauty to eliminate graph isomorphisms [20, 21]. To check isomorphisms of graphs, we use the IsomormicQ command of the Combinatorica package of the Mathematica 8.0 program [19]. We use the following result: Lemma 3. Let F1,F2and F3be three graphs. If S(F1) = ∅,F3is a subgraph of F1with V(F3) = V(F1)and F3is an induced subgraph of F2, then S(F2) = ∅. Proof. Applying Algorithm 2 we obtain S(F3) from S(F1), thus S(F3) = ∅, and applying Algorithm 1 we obtain S(F2) from S(F3), hence S(F2) = ∅. In order to prove that for any P4-free graph Fof order 14, S(F) = ∅, without loss of generality we can assume that the components of Fare K2,K3or K1,n, with n⩾3, because if K1or P3are components of F, there exists a graph F0or order 14 such that F is a subgraph of F0and K1and P3are not components of F0. Thus, if S(F0) = ∅then, applying Algorithm 2, we have that S(F) = ∅. Since R(C4, K4) = 10 [7], F0has no independent set of order 10 and, since R(P3, C4, K4) = 13, F0has at least two components different of K2. Thus, it is easy to check that F0∈ {4K3∪K2,3K3∪K1,4,2K3∪K1,7,2K3∪K1,5∪K2,2K3∪2K1,3,2K3∪K1,3∪ 2K2,2K3∪4K2, K3∪K1,6∪2K2, K3∪K1,4∪K1,3∪K2, K3∪K1,4∪3K2,2K1,3∪3K2}. From Lemma 3, we obtain: Corollary 4. If S(K3∪2K2∪5K1) = ∅then S(2K3∪K1,7),S(2K3∪K1,5∪K2),S(K3∪ K1,6∪2K2),S(K3∪K1,4∪K1,3∪K2)and S(2K1,3∪3K2) = ∅. Proof. Let F1=K3∪2K2∪5K1. Considering F3=K3∪2K2∪5K1we have that S(2K3∪K1,5∪K2), S(K3∪K1,6∪2K2) = ∅. Considering F3=K3∪K2∪7K1we obtain that S(2K3∪K1,7), S(K3∪K1,4∪K1,3∪K2) = ∅. Finally, considering F3= 3K2∪6K1 we obtain that S(2K1,3∪3K2) = ∅. Corollary 5. If S(2K3∪3K2∪K1) = ∅then S(2K3∪K1,3∪2K2),S(2K3∪4K2), S(K3∪K1,4∪3K2) = ∅. Proof. Let F1= 2K3∪3K2∪K1. Considering F3= 2K3∪3K2∪K1we have that S(2K3∪4K2) = ∅. Considering F3= 2K3∪2K2∪3K1we obtain that S(2K3∪K1,3∪2K2) = ∅. Finally, considering F3=K3∪3K2∪4K1we obtain that S(K3∪K1,4∪3K2) = ∅. Consequently, we have that if S(F) = ∅for any F∈ F ={4K3∪K2,3K3∪K1,4,2K3∪ 2K1,3, K3∪2K2∪5K1,2K3∪3K2∪K1}then R(P4, C4, K4) = 14. Now, we are going to prove the main result of this subsection. Theorem 6. R(P4, C4, K4) = 14. the electronic journal of combinatorics 19(4) (2012), #P47 6 Proof. It is enough to prove that for any F∈ F then S(F) = ∅. There is a coloring in S(5K1) for every (C4, K4; 5)-coloring, thus |S(5K1)|= 13. From this set, applying Algorithm 1, we obtain the sets S(K2∪4K1), S(2K2∪3K1), S(3K2∪ 2K1), S(4K2∪K1), S(5K2), S(K3∪4K2), S(2K3∪3K2), the cardinalities of which are 122, 1012, 4808, 8569, 2676, 7466 and 968. From S(2K3∪3K2), applying Algorithm 2, we generate the sets S(2K3∪2K2∪2K1), S(2K3∪K2∪4K1) and S(2K3∪6K1), the cardinalities of which are 944, 84 and 1. From S(2K3∪6K1), applying Algorithm 1, we obtain the sets S(2K3∪K1,3∪3K1), and S(2K3∪2K1,3), the cardinalities of which are 5 and 0, respectively. Thus S(2K3∪2K1,3) = ∅. From S(2K3∪K2∪4K1), applying Algorithm 2, we obtain that S(K3∪2K2∪5K1) = ∅. From S(2K3∪3K2), applying Algorithm 1, we generate the set S(3K3∪2K2). Its cardinality is 1. From S(3K3∪2K2), applying Algorithm 2, we obtain S(3K3∪K2∪2K1) and S(3K3∪4K1). Their cardinalities are 2 and 1. From S(3K3∪4K1), applying Algorithm 1, we have that S(3K3∪K1,4) = ∅. From S(3K3∪2K2), applying Algorithm 1, we obtain that S(4K3∪K2) = ∅and, finally, from S(3K3∪2K2), applying Algorithm 2, we have that S(2K3∪3K2∪K1) = ∅. 3.2 R(C4, H1, H2) To generate subfamilies of (C4, H1, H2;n), where H1, H2∈ {K3, K4−e}we used the following algorithm. Algorithm 7.Extension Input: coloring G∈(C4, H1, H2;n) Output: set of all one-vertex extensions of Gwhich belong to (C4, H1, H2;n+ 1) For R(C4, K4−e, K3) we used the next algorithm. Let H−=K2if H=K3, and H−=P3if H=K4−e. Algorithm 8.Merge Input: coloring G1∈(C4, H, P3;n) and G2∈(C4, H−, K4−e;m) Output: set of all colorings G∈(C4, H, K4−e;n+m+ 1) such that G1=G[N2(v)] and G2=G[N3(v)] Algorithm 7 is a standard procedure in graph theoretical computations. In case of generated subfamilies of (C4, H1, H2;n), where H1, H2∈ {K3, K4−e}we cannot use it alone because we would have to keep collections of nonisomorphic colorings which are to large. Algorithm 7 is used to determine the collections of colorings (C4, P3, K3;n) for n⩽7, (C4, K4−e, K2;n) for n⩽6 and (C4, P3, K4−e;n) for n⩽8. The colorings from these collections were used as the parameters of Algorithm 8. Both of these algorithms are often used to determine Ramsey numbers (see [2, 25]) therefore we do not discuss them in detail. Let t(n) denote the maximum number of edges of a graph with nvertices not containing aC4as a subgraph. Theorem 9. R(C4, K4−e, K3) = 17. 7 Proof. Since R(C4, K4−e, K3)⩾R(C4, K3, K3) = 17 [11], we obtain the lower bound. To obtain the upper bound we use the following computations. Since R(C4, P3, K3)=8 and R(C4, K4−e, K2) = 7 [1], then for every vertex uwe have d2(u)⩽7 and d3(u)⩽6. Since t(17) = 36 [8], then every coloring of (C4, K4−e, K3; 17) must contain a vertex v such that d1(v)⩽4. There are only 3 possibilities: •There exists a vertex vsuch that d1(v) = 3, d2(v) = 7 and d3(v) = 6. We use Algorithm 8 for every graph G1∈(C4, P3, K3; 7) and G2∈(C4, K4−e, K2; 6) and find 8 colorings of (C4, K4−e, K3; 14). Next we use Algorithm 7 to one-vertex extensions of these 8 colorings and obtain subfamilies of (C4, K4−e, K3;n) for n∈ {15,16,17}. Cardinalities of these sets are 6, 43, 0, respectively. •There exists a vertex vsuch that d1(v) = 4, d2(v) = 7 and d3(v) = 5. Similarly, for every G1∈(C4, P3, K3; 7) and G2∈(C4, K4−e, K2; 5) we found 26355 colorings of (C4, K4−e, K3; 13). Next, we computed subsets of (C4, K4−e, K3;n) for n∈ {14,15,16,17}, the cardinalities of which are 470854, 515882, 3444, 0, respectively. •There exists a vertex vsuch that d1(v) = 4, d2(v) = 6 and d3(v) = 6. Again, for every G1∈(C4, P3, K3; 6) and G2∈(C4, K4−e, K2; 6) we found 132266 colorings of (C4, K4−e, K3; 13). Next, we computed subsets of (C4, K4−e, K3;n) for n∈ {14,15,16,17}, the cardinalities of which are 4077662, 8109281, 56653, 0, respectively. Finally, this means that (C4, K4−e, K3; 17) = ∅and R(C4, K4−e, K3) = 17. In order to prove some Theorems 11 and 13, we use the following lemma: Lemma 10. Let Fbe a graph of order nand let v1, v2, v3∈V(F), such that vi, for i= 1,2,3, is adjacent to at least bn 3c+ 1 vertices of V(F)\{v1, v2, v3}. Then C4is a subgraph of G. Proof. Let aibe the number of vertices of V(F)\{v1, v2, v3}adjacent to viand nonadjacent to the other two vertices of {v1, v2, v3}, let bi,j be the number of vertices of V(F)\{v1, v2, v3}adjacent to viand vjand non-adjacent to the other one vertex of {v1, v2, v3}and let c1,2,3be the number of vertices of V(F)\{v1, v2, v3}adjacent to v1, v2and v3. Then a1+a2+a3+b1,2+b1,3+b2,3+c1,2,3⩽n−3. Since viis adjacent at least to bn 3c+1 vertices of V(G)\{v1, v2, v3}, we have that a1+b1,2+b1,3+c1,2,3⩾bn 3c+1, a2+b1,2+b2,3+c1,2,3⩾bn 3c+1 and a3+b1,3+b2,3+c1,2,3⩾ bn 3c+ 1. Consequently, a1+a2+a3+ 2b1,2+ 2b1,3+ 2b2,3+ 3c1,2,3⩾3bn 3c+ 3 ⩾n+ 1 and b1,2+b1,3+b2,3+ 2c1,2,3⩾4. Then there are iand jsuch that bi,j +c1,2,3⩾2, viand vj have at least two common neighbors belonging to V(F)\{v1, v2, v3}and C4is a subgraph of F. 8 We prove that adding an edge to K3leaves its Ramsey number unchanged, such as in the following theorem. Theorem 11. R(C4, K4−e, K3+e) = R(C4, K4−e, K3) = 17. Proof. By Theorem 9 and by the monotonicity of Ramsey numbers we have that 17 = R(C4, K4−e, K3)⩽R(C4, K4−e, K3+e). Assume, towards a contradiction, that R(C4, K4−e, K3)< R(C4, K4−e, K3+e). Let Gbe a (C4, K4−e, K3+e; 17)- coloring. There is a green triangle in G. Let {v1, v2, v3}be the vertices of a green triangle of G. Since R(C4, P3, K3+e) = 8 [1], then |N2(vi)|⩽7 and |N1(vi)|⩾7 for i∈ {1,2,3}. By Lemma 10, we obtain a red C4, a contradiction. Theorem 12. R(C4, K4−e, K4−e) = 19. Proof. Lower bound R(C4, K4−e, K4−e)⩾19 is presented in [9]. To obtain the upper bound we use similar computations as in the proof of Theorem 9. Since R(C4, P3, K4−e) = R(C4, K4−e, P3) = 9 [1], then for every vertex uwe have d2(u)⩽8 and d3(u)⩽8. Since t(19) = 42 [8], then every coloring of (C4, K4−e, K3; 19) must contain vertex vsuch that d1(v)⩽4. There are only 4 possibilities: •There is a vertex vsuch that d1(v) = 4, d2(v) = 7 and d3(v) = 7. We use Algorithm 8 for every graph G1∈(C4, P3, K4−e; 7) and G2∈(C4, K4− e, P3; 7) and find 621308 colorings of (C4, K4−e, K4−e; 15). Next, we use Algorithm 7 to one-vertex extensions of these colorings and obtain subfamilies of (C4, K4−e, K3;n) for n∈ {16,17,18,19}. Cardinalities of these sets are 731002, 18285, 7, 0, respectively. •There is a vertex vsuch that d1(v) = 4, d2(v) = 8 and d3(v) = 6, (a case in which d2(v) = 6 and d3(v) = 8 is symmetrical). Similarly, for every G1∈(C4, P3, K4−e; 8) and G2∈(C4, K4−e, P3; 6) we found 10488 colorings of (C4, K4−e, K4−e; 15). Next, we computed subsets of (C4, K4− e, K4−e;n) for n∈ {16,17,18}, the cardinalities of which are 28733, 1807, 0, respectively. •There is a vertex vsuch that d1(v) = 3, d2(v) = 8 and d3(v) = 7, (a case in which d2(v) = 7 and d3(v) = 8 is symmetrical). In this case Algorithm 8 returns an empty set of colorings. •There is a vertex vsuch that d1(v) = 2, d2(v) = 8 and d3(v) = 8. In this case Algorithm 8 returns an empty set of colorings. We state that set (C4, K4−e, K4−e; 19) = ∅and R(C4, K4−e, K4−e) = 19. Also, we have: Theorem 13. R(C4, K3+e, K4)⩽max{R(C4, K3, K4),29}⩽32. 9 5 Appendix X022122211212 0X22221202212 22X2111022222 222X221220120 1212X12021222 22121X0122222 211120X222112 2202012X12021 10222221X2211 122012222X120 2221221021X21 11222212122X2 222022211012X Figure 1: Matrix of (P4, C4, K4; 13)-coloring. X21211112222101200212202112 2X2211221110122220022011122 12X112222110210202222110200 221X22221022101122221021110 1112X0220221222111101021202 11220X222221012211121222021 122222X01102120110201211222 1222220X1112022111200211222 21210211X221202021202120221 211022112X01221222121002212 2112220120X1220222111202211 20021122111X122222022110122 112120102221X12201120222021 0210212202221X1122221221010 12012202210221X211222112001 222112110222212X20210120221 0202111122220212X0212122112 00221101122212100X212022112 202211222110122222X20112122 1222020002122221112X1211222 22211110211201202201X202120 201002221021221110122X21202 0112221120012212221102X2212 21011211022021202221212X221 112120222221000211121222X21 1201022221122102112220122X1 22002122121210112222022111X Figure 2: Matrix of (C4, K4−e, K4; 27)-coloring.