ARS MATHEMATICA CONTEMPORANEA ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 15 (2018) 355-373 https://doi.org/10.26493/1855-3974.1223.b26 (Also available at http://amc-journal.eu) The thickness of Ki,n?n and K2, * Xia Guo School of Mathematics, Tianjin University, Tianjin, P.R.China Yan Yang t School ofMathematics, Tianjin University, Tianjin, P.R.China Received 26 October 2016, accepted 12 June 2018, published online 9 July 2018 The thickness of a graph G is the minimum number of planar subgraphs whose union is G. In this paper, we obtain the thickness of complete 3-partite graph Kl,n,n, K2,n,n and complete 4-partite graph Kljl n n. Keywords: Thickness, complete 3-partite graph, complete 4-partite graph. Math. Subj. Class.: 05C10 1 Introduction The thickness 6(G) of a graph G is the minimum number of planar subgraphs whose union is G. It was first defined by W. T. Tutte [7] in 1963, then a few authors obtained the thickness of hypercubes [5], complete graphs [1, 2, 8] and complete bipartite graphs [3]. Naturally, people wonder about the thickness of the complete multipartite graphs. A complete k-partite graph is a graph whose vertex set can be partitioned into k parts, such that every edge has its ends in different parts and every two vertices in different parts are adjacent. Let KPlP2..Pk denote a complete k-partite graph in which the ith part contains p (1 < i < k) vertices. For the complete 3-partite graph, Poranen proved 6(Kn,n,n) < \nl in [6], then Yang [10] gave a new upper bound for 6(Kn,n,n), i.e., 6(Kn,n,n) < \n+11 + 1 and obtained 6(K„i„i„) = [], when n = 3 (mod 6). And also Yang [9] gave the thickness number of Kl,mn(l < m < n) when l + m < 5 and showed that 6(Ki,m,n) = \1 when l + m is even and n > l(l + m - 2)2; or l + m is odd and n > (l + m - 2)(l + m - 1). In this paper, we obtain the thickness of complete 3-partite graph K1n n and K2 n n, and we also deduce the thickness of complete 4-partite graph K1i1n n from that of K2 n n. *Supported by the National Natural Science Foundation of China under Grant No. 11401430. t Corresponding author. E-mail addresses: guoxia@tju.edu.cn (Xia Guo), yanyang@tju.edu.cn (Yan Yang) Abstract ©® This work is licensed under https://creativecommons.Org/licenses/by/3.0/ 356 Ars Math. Contemp. 15 (2018) 441-466 2 The thickness of K1,n,n In [3], Beineke, Harary and Moon gave the thickness of complete bipartite graphs Km for most value of m and n, and their theorem implies the following result immediately. Lemma 2.1 ([3]). The thickness of the complete bipartite graph Kn ' n + 2" is 0(Kn,n) 4 In [4], Chen and Yin gave a planar decomposition of the complete bipartite graph K4p,4p with p + 1 planar subgraphs. Figure 1 shows their planar decomposition of K4p,4p, in which {u1,..., u4p} = U and {v1,..., v4p} = V are the 2-partite vertex sets of it. Based on their decomposition, we give a planar decomposition of K2,n,n with p + 1 subgraphs when n = 0 or 3 (mod 4) and prove the following lemma. (a) The graph Gr (1 < r < p). ul u2 vl v2 u4p-1 u4p v4p-1 v4p (b) The graph Gv+1. Figure 1: A planar decomposition of K4p,4p. Lemma 2.2. The thickness of the complete 3-partite graph K1,n,n and K2,n,n is ' n + 2 " 0(Ki,n,n) = 0(K2,n,n) = 4 when n = 0 or 3 (mod 4). Proof. Let the vertex partition of K2,n,n be (X,U,V), where X = {x1,x2}, U = {ui,..., un} and V = {vi,..., v„|. X. Guo and Y. Yang: The thickness of Ki,„,„ and K2,n,n 357 When n = 0 (mod 4), let n = 4p (p > 1). Let {Gi,..., Gp+1} be the planar decomposition of Kn,n constructed by Chen and Yin in [4]. As shown in Figure 1, the graph Gp+1 consists of n paths of length one. We put all the n paths in a row, place vertex x1 on one side of the row and the vertex x2 on the other side of the row, join both x1 and x2 to all vertices in Gp+1. Then we get a planar graph, denote it by Gp+1. It is easy to see that {G1,..., Gp, Gp+1} is a planar decomposition of K2,n,n. Therefore, we have 0(K2,n,n) < p +1. Since Kn,n c K1n n c K2,n,n, combining it with Lemma 2.1, we have p + 1 = 0(Kn,n) < 0(K1,n,n) < 0(K2,n,n) < P +1, that is, 0(K^n,n) = 0(K2,n,n) = p +1 when n = 0 (mod 4). When n = 3 (mod 4), then n = 4p + 3 (p > 0). When p = 0, from [9], we have 0(^,3,3) = 0(K2,3,3) = 2. Whenp > 1, since Kn,n c K1,n,n c K2,n,n C K2 according to Lemma 2.1 and 0(K2,4p,4p) = p + 1, we have p + 2 = 0(Kn,n) < 0(K1,n,n) < 0(K2,n,n) < 0(K2,n+1,n+1) = p + 2. Then, we get 0(K1,n,n) = 0(K2,n,n) = p + 2 when n = 3 (mod 4). Summarizing the above, the lemma is obtained. □ Lemma 2.3. There exists a planar decomposition of the complete 3-partite graph K1,4p+2,4p+2 (p > 0) with p + 1 subgraphs. Proof. Suppose the vertex partition of the complete 3-partite graph K1,n,n is (X, U, V), where X = {x}, U = {u1,..., un} and V = {v1,..., vn}. When n = 4p + 2, we will construct a planar decomposition of K1,4p+2,4p+2 with p + 1 planar subgraphs to complete the proof. Our construction is based on the planar decomposition {G1, G2,..., Gp+1} of K4p 4p given in [4], as shown in Figure 1 and the reader is referred to [4] for more details about this decomposition. For convenience, we denote the vertex set Uf=1i=r{u4i_3, u4i-2}^p=1,i=r{u4i-1,u4i}^P=1,i=r{v4i_3,v4i_1} and |JP=Wr{v4i_2,v4i} by U1, UJ, V1r and V2r respectively. We also label some faces of Gr (1 < r < p), as indicated in Figure 1, for example, the face 1 is bounded by v4r_3u4rvju4r_1 in which vj is some vertex from Vf. In the following, for 1 < r < p + 1, by adding vertices x, u4p+1, u4p+2, v4p+1, v4p+2 and some edges to Gr, and deleting some edges from Gr such edges will be added to the graph Gp+1, we will get a new planar graph Gr such that {G?1,..., Gp+1} is a planar decomposition of K1,4p+2,4p+2. Because v4r_3 and v4r-1 in Gr (1 < r < p) is joined by 2p - 2 edge-disjoint paths of length two that we call parallel paths, we can change the order of these parallel paths without changing the planarity of Gr. For the same reason, we can do changes like this for parallel paths between M4r-1 and u4r, v4r_2 and v4r, u4r_3 and u4r_2. We call this change by parallel paths modification for simplicity. All the subscripts of vertices are taken modulo 4p, except that of v4p+1, v4p+2, w4p+1 and u4p+2 (the vertices we added to Gr). Case 1. When p is even and p > 2. (a) The construction for Gr , 1 < r < p, and r is odd. Step 1: Place the vertex x in the face 1 of Gr, delete edges v4r_3u4r and u4rv4r_1 from Gr. Do parallel paths modification, such that w4r+6 G U[, v4r+1 G Vf and 358 Ars Math. Contemp. 15 (2018) 441-466 u4r, v4r-3, v4r-2, v4r-1 are incident with a common face which the vertex x is in. Join x to «4r-3, «4r-1, «4r, ^4r-3, V4r-2, ^4r-1 and «4r+6, V4r + 1. Step 2: Do parallel paths modification, such that w4r+11, u4r+12 € U2 are incident with a common face. Place the vertex v4p+1 in the face, and join it to both w4r+11 and w4r+12. Step 3: Do parallel paths modification, such that w4r+7, u4r+8 € UJ are incident with a common face. Place the vertex v4p+2 in the face, and join it to both w4r+7 and w4r+8. Step 4: Do parallel paths modification, such that v4r+10, v4r+12 € V2r are incident with a common face. Place the vertex w4p+1 in the face, and join it to both v4r+10 and v4r+12. Step 5: Do parallel paths modification, such that v4r+6, v4r+8 € V2r are incident with a common face. Place the vertex w4p+2 in the face, and join it to both v4r+6 and v4r+8. (b) The construction for Gr, 1 < r < p, and r is even. Step 1: Place the vertex x in the face 3 of Gr, delete edges v4rw4r-3 and w4r-3v4r_2 from Gr. Do parallel paths modification, such that w4r+7 € U2, v4r+4 € V2r and u4r-3, u4r-2, u4r, v4r-2, v4r-1, v4r are incident with a common face which the vertex x is in. Join x to U4r—3, W4r_2, U4r, V4r_2, V4r — 1, V4r and U4r+7, V4r+4. Step 2: Do parallel paths modifications, such that w4r+5,w4r+6 € U[, u4r+1,w4r+2 € U[, v4r+5, v4r+7 € Vf, v4r+1, v4r+3 € Vf are incident with a common face, respectively. Join v4p+1 to both w4r+5 and u4r+6, join v4p+2 to both w4r+1 and u4r+2, join w4p+1 to both v4r+5 and v4r+7, join u4p+2 to both v4r+1 and v4r+3. Table 1 shows how we add edges to Gr (1 < r < p) in Case 1. The first column lists the edges we added, the second and third column lists the subscript of vertices, and we also indicate the vertex set which they belong to in brackets. Table 1: The edges we add to Gr (1 < r < p) in Case 1. subscript \ case edge r is odd r is even XUj 4r — 3, 4r — 1, 4r 4r + 6 (Uf) 4r — 3,4r — 2,4r 4r + 7 (UJ ) xvj 4r — 3, 4r — 2, 4r — 1 4r + 1 (Vf ) 4r — 2,4r — 1,4r 4r + 4 (V2r) V4p+lUj 4r + 11, 4r + 12 (UJ) 4r + 5,4r + 6 (UJ) V4p+2Uj 4r + 7, 4r + 8 (U2r) 4r + 1,4r + 2 (UJ) U4p+1Vj 4r + 10, 4r + 12 ( V2r) 4r + 5, 4r + 7 (Vf ) U4p+2 Vj 4r + 6, 4r + 8(V2r) 4r +1, 4r + 3 (Vf ) (c) The construction for Gp+1. From the construction in (a) and (b), the subscript set of u that xuj is an edge in Gr for some r G {1,... ,p} is {4r — 3, 4r — 1,4r, 4r + 6 (mod 4p) | 1 < r < p, and r is odd} U {4r — 3, 4r — 2,4r, 4r + 7 (mod 4p) | 1 < r < p, and r is even} = {1,... ,p}. X. Guo and Y. Yang: The thickness of Ki,„,„ and K2,n,n 359 The subscript set of uj that v4p+1uj is an edge in Gr for some r G {1,...,p} is {4r + 11,4r +12 (mod 4p) | 1 < r < p, and r is odd} U {4r + 5,4r + 6 (mod 4p) | 1 < r < p, and r is even} = {4r — 3, 4r — 2,4r — 1, 4r | 1 < r < p, and r is even}. Using the same procedure, we can list all the edges incident with x, v4p+1, v4p+2, u4p+1 and u4p+2 in Gr (1 < r < p), so we can also list the edges that are incident with x, v4p+1, v4p+2, u4p+1 in K1j4p+2j4p+2 but not in any Gr (1 < r < p). Table 2 shows the edges that belong to K1j4p+2j4p+2 but not to any Gr, 1 < r < p, in which the the fourth and fifth rows list the edges deleted form Gr (1 < r < p) in step one of (a) and (b), and the sixth row lists the edges of Gp+1. The Gp+1 is the graph consists of the edges in Table 2, Figure 2 shows Gp+1 is a planar graph. Table 2: The edges of Gp+1 in Case 1. edges subscript xvip+1,xuip+1,vip+1uj ,'Uip+1Vj j = 4r - 3, 4r - 2, 4r - 1, 4r, 4p + 2 (r = 1, 3,..., p - 1) XV4p+2,XU4p+2,V4p+2Uj, U4p+2 Vj j = 4r - 3,4r - 2,4r - 1,4r, 4p + 1 (r = 2,4,... ,p) V4r —3U4r, U4rV4r-i r = 1, 3,..., p - 1 V4rU4r-3, U4r_3V4r_2 r = 2, 4,... ,p Uj Vj j = 1,..., 4p + 2 u4p + 1 v4p + 2 Figure 2: The graph Gp+1 in Case 1. A planar decomposition {G?1,..., G?p+1} of K1j4p+2j4p+2 is obtained as above in this case. In Figure 3, we draw the planar decomposition of K11818, it is the smallest example for the Case 1. We denote vertex u4 and v by i and i' respectively in this figure. Case 2. When p is odd and p > 3. The process is similar to that in Case 1. (a) The construction for Gr, 1 < r < p, and r is odd. Step 1: Place the vertex x in the face 1 of Gr, delete edges v4r-3u4r and u4rv4r-1 from Gr, for 1 < r < p, and delete v2u1 from G1 additionally. 360 Ars Math. Contemp. 15 (2018) 441-466 (e) The graph G5. Figure 3: A planar decomposition of K11818. X. Guo and Y. Yang: The thickness of Ki,„,„ and K2,n,n 361 For 1 < r < p, do parallel paths modification to Gr, such that u4r+6 € U[, v4r+1 G V and u4r-3, u4r-1, u4r, v4r-3, v4r-2, v4r-1 are incident with a common face which the vertex x is in. Join x to u4r-3, u4r-1, u4r, v4r-3, v4r-2, v4r-1 and u4r+6, v4r+1. Similarly, in G1, join x to u1, u3, u4, v1, v2, v3, v4 and u10 G U/, v5 G V1. In Gp, join X to M4p-3,M4p-1,U4p,V4p_3,V4p_2,V4p_1 and «2 G Up. Step 2: For 1 < r < p, do parallel paths modification to Gr, such that u4r+11, u4r+12 G U2, w4r+7,w4r+8 G Ur, v4r+10, v4r+12 G V2r and v4r+6,v4r+8 G V2r are incident with a common face, respectively. Join v4p+1 to both w4r+11 and w4r+12, join v4p+2 to both u4r+7 and u4r+8, join w4p+1 to both v4r+10 and v4r+12, join w4p+2 to both v4r+6 and V4r+8. Similarly, in Gp, join v4p+1 to u5, u6 G Uf, join v4p+2 to u7, u8 G Uf, join w4p+1 to V6, V8 G V2p, join «4f+2 to V5, V7 G V1p. (b) The construction for Gr, 1 < r < p, and r is even. Step 1: Place the vertex x in the face 3 of Gr, delete edges v4ru4r-3 and u4r-3v4r-2 from Gr, 1 < r < p - 1. Do parallel paths modification to Gr, 1 < r < p-1, such that u4r+7 G U2, v4r+4 G V2r and u4r-3, u4r-2, u4r, v4r-2, v4r-1, v4r are incident with a common face which the vertex x is in. Join x to u4r-3, u4r-2, u4r, v4r-2, v4r-1, v4r and u4r+7, v4r+4. Similarly, in Gp-1,join x to u4p-7, u4p-6, u4p-4, v4p-6, v4p-5, v4p-4 and u7 G Up 1, v4p G V2p 1. Step 2: Do parallel paths modifications, such that u4r+5,«4r+6 G U[, «4r+1, «4r+2 G U[, v4r+5,v4r+7 G Vf, v4r+1, v4r+3 G vr are incident with a common face, respectively. Join v4p+ 1 to both u4r+5 and u4r+6, join v4p+2 to both u4r+1 and u4r+2, join u4p+ 1 to both v4r+5 and v4r+7, join u4p+2 to both v4r+ 1 and v4r+3. Table 3 shows how we add edges to Gr (1 < r < p) in Case 2. (c) The construction for Gp+1. With a similar argument to that in Case 1, we can list the edges that belong to K1,4p+2,4p+2 but not to any Gr, 1 < r < p, in this case, as shown in Table 4. Then Gp+1 is the graph that consists of the edges in Table 4. Figure 4 shows Gp+1 is a planar graph. Therefore, {G1,..., Gp+1} is a planar decomposition of K14p+2 4p+2 in this case. Figure 4: The graph Gp+1 in Case 2. 362 Ars Math. Contemp. 15 (2018) 441-466 Table 3: The edges we add to Gr (1 < r < p) in Case 2. subscript \ case r is odd r is even edge XUj 4r - 3, 4r - 1, 4r 4r + 6, r = p (Uf) 2, r = p (Uf) 4r - 3, 4r - 2, 4r 4r + 7, r = p - 1 (U2r) 7, r = p - 1 (UJ) XVj 4r - 3, 4r - 2, 4r - 1 4, 5, r = 1 4r + 1, r = 1,p (V) 4r - 2, 4r - 1, 4r 4r + 4(V2r) V4p+lUj 4r +11,4r + 12, r = p (U2r) 5, 6, r = p (Uf) 4r + 5,4r + 6 (Uf) V4p+2Uj 4r + 7,4r + 8 (U2r) 4r + 1,4r + 2 (Uf) U4p+lVj 4r + 10,4r + 12, r = p (V2r) 6, 8, r = p (V2r) 4r + 5, 4r + 7 (Vxr) U4p+2Vj 4r + 6,4r + 8, r = p (V2r) 5, 7, r = p (Vf) 4r + 1, 4r + 3 (Vxr) Table 4: The edges of Gp+\ in Case 2. edges subscript XV4p+ l, V4p+ l Uj j = 4r - 3,4r - 2,4r - 1,4r, 7, 8,4p +2 (r = 3, 5, 7,... ,p) XU4p+ i ,U4p+ i Vj j = 4r - 3,4r - 2,4r - 1,4r, 5, 7,4p + 2 (r = 3, 5, 7, . . . , p) XV4p+2, V4p+2Uj j = 4r - 3,4r - 2,4r - 1,4r, 5, 6,4p + 1 (r = 1,4, 6, 8,... ,p - 1) XU4p+2,U4p+2Vj j = 4r - 3,4r - 2,4r - 1,4r, 6, 8,4p + 1 (r = 1,4, 6, 8,... ,p - 1) U 1V2, V4f_3U4r, U4rV4r_ i r = 1, 3,... ,p V4rU4r—3 , U4r_3V4r_2 r = 2,4,... ,p - 1 Uj Vj j = 1,... ,4p + 2 X. Guo and Y. Yang: The thickness of Ki,„,„ and K2,n,n 363 Case 3. When p < 3. When p = 0, Kij2j2 is a planar graph. When p = 1,2,3, we give a planar decomposition for Ki,6,6, Kiiio,io and K1i14i14 with 2, 3 and 4 subgraphs respectively, as shown in Figure 5, Figure 6 and Figure 7. Figure 5: A planar decomposition of Kij6j6. Figure 6: A planar decomposition of Ki,i0ii0. Lemma follows from Cases 1, 2 and 3. □ 364 Ars Math. Contemp. 15 (2018) 441-466 v4p + 1 X2 Figure 8: The graph Gp+1 in Case 1. X. Guo and Y. Yang: The thickness of Ki,„,„ and K2,n,n 365 Theorem 2.4. The thickness of the complete 3-partite graph Kiin,n is ' n + 2 ~ 4 Proof. When n = 4p, 4p + 3, the theorem follows from Lemma 2.2. When n = 4p + 1, n = 4p +2, from Lemma 2.3, we have 0(K1,4p+2,4p+2) < p +1. Since 0(^4^,4^) = p +1 and K^p c #1,4^+1,4^+1 c #1,4^+2,4^+2, we obtain p +1 < 0(^1,4^+1,4^+1) < 0(#1,4p+2,4p+2) < p +1. Therefore, 0(KMp+1,4p+1) = 0(#1,4p+2,4p+2) = p + 1. Summarizing the above, the theorem is obtained. □ 3 The thickness of K2,n,n Lemma 3.1. There exists a planar decomposition of the complete 3-partite graph K2,4p+1,4p+1 (p > 0) with p + 1 subgraphs. Proof. Let (X, U, V) be the vertex partition of the complete 3-partite graph K2,n,n, in which X = {x1, x2}, U = {u1,..., un} and V = {v1,..., vn}. When n = 4p + 1, we will construct a planar decomposition of K2,4p+1,4p+1 with p +1 planar subgraphs. The construction is analogous to that in Lemma 2.3. Let {G1, G2,..., Gp+1} be a planar decomposition of K4p,4p given in [4]. In the following, for 1 < r < p + 1, by adding vertices x1, x2, u4p+1, v4p+1 to Gr, deleting some edges from Gr and adding some edges to Gr, we will get a new planar graph Gr such that {G?1,..., G?p+1} is a planar decomposition of K2,4p+1,4p+1. All the subscripts of vertices are taken modulo 4p, except that of u4p+1 and v4p+1 (the vertices we added to Gr). Case 1. When p is even and p > 2. (a) The construction for Gr , 1 < r < p. Step 1: When r is odd, place the vertex x1, x2 and u4p+1 in the face 1, 2 and 5 of Gr respectively. Delete edges v4r-3w4r and M4r-1v4r-2 from Gr. When r is even, place the vertex x1, x2 and u4p+1 in the face 3, 4 and 5 of Gr, respectively. Delete edge v4rw4r-3 and M4r-2v4r-1 from Gr. Step 2: Do parallel paths modifications, then join x1, x2, u4p+1 and v4p+1 to some Wj and vj, as shown in Table 5. (b) The construction for 3. (a) The construction for Gr, 1 < r < p. Step 1: When r is odd, place the vertex x^ x2 and u4p+1 in the face 1, 2 and 5 of Gr respectively. Delete edges v4r-3u4r and u4r-1v4r_2 from Gr. When r is even, place the vertex x1, x2 and u4p+1 in the face 3, 4 and 5 of Gr, respectively. Delete edge v4ru4r-3 and u4r_2v4r-1 from Gr. Step 2: Do parallel paths modifications, then join x1, x2, u4p+1 and v4p+1 to some uj and vj, as shown in Table 7. Table 7: The edges we add to Gr (1 < r < p) in Case 2. subscript \ case edge r is odd r is even Xl Uj 4r - 1, 4r 4r + 5, r = p (U[) 1, r = p (U2) 4r - 3, 4r - 2 4r + 8, r = p - 1 (U22) 8, r = p - 1 (U2) X1 Vj 4r - 3, 4r - 1 4r + 1,r = p (Vl2 ) 4r - 2, 4r 4r + 4 (V2) X2 Uj 4r - 1, 4r 4r + 3, r = p (U22) 8, r = p (U2) 4r - 3, 4r - 2 4r + 2 (Ul2) x2 vj 4r - 2, 4r 4r + 7,r = p (Vl2) 3, r = p (Vl2) 4r - 3, 4r - 1 4r + 6, r = p - 1 (V22) 6, r = p - 1 (V22) U4p+lVj 4r - 2,4r - 1 V4p+lUj 4r + 4,4r + 8, r = p (U22) 4, r = p (U2) 4r - 11,4r - 7 (Uf ) (b) The construction for Gp+1. We list the edges that belong to K2j4p+1j4p+1 but not to any Gr, 1 < r < p, as shown in Table 8. Then Gp+1 is the graph that consists of the edges in Table 8. Figure 10 shows Gp+1 is a planar graph. Therefore, |G?1,..., Gp+1} is a planar decomposition of K2j4p+1j4p+1 in this case. Case 3. When p < 3. When p = 0, K2j1j1 is a planar graph. When p = 1,2, 3, we give a planar decomposition for K2j5j5, K2j9j9 and K21313 with 2, 3 and 4 subgraphs respectively, as shown in Figure 11, Figure 12 and Figure 13. Summarizing Cases 1, 2 and 3, the lemma follows. □ X. Guo and Y. Yang: The thickness of Ki,„,„ and K2,n,n 369 Table 8: The edges of Gp+1 in Case 2. edges subscript Xl Uj j = 2,4r + 3,4r + 6,4p + 1 (r = 1, 3,... ,p - 2) Xi Vj j = 2, 4,4r + 3, 4r + 6,4p + 1 (r = 1, 3,... ,p - 2) XX 2 Uj j = 1, 2, 9,4r, 4r + 1,4p + 1 (r = 4,... ,p - 1) x2 vj j = 1, 8, 9,4r, 4r + 1,4p + 1 (r = 4,... ,p - 1) U4p+lVj j = 4r - 3,4r (r = 1, 2,...,p) V4p+lUj j = 4r - 2,4r - 1,4p - 7 (r = 1, 2,...,p) V4r-3U4r, V4r-2U4r_1 r = 1, 3,... ,p U4r-3V4r, U4r-2V4r-1 r = 2,4,... ,p - 1 Uj Vj j = 1,... , 4p + 1 Figure 10: The graph Gp+1 in Case 2. Figure 11: A planar decomposition K2,5,5. 37G Ars Math. Contemp. 1S (2G1S) 3SS-373 X. Guo and Y. Yang: The thickness of Ki,„,„ and K2,n,n 371 Figure 13: A planar decomposition of K2,13,13. 373 Ars Math. Contemp. 15 (2018) 441-466 Theorem 3.2. The thickness of the complete 3-partite graph K2i„in is ~ n + 3 - 0(K2,n,n) = 4 Proof. When n = 4p, 4p + 3, from Lemma 2.2, the theorem holds. When n = 4p +1, from Lemma 3.1, we have 0(K2i4p+1j4p+1) < p +1. Since 0(K4p,4p) = p + 1 and K^p c K2,4p+i,4p+i, we have p + 1 = 0(K4p,4p) < 0(K2,4p+1,4p+i) < P +1. Therefore, 0(K2,4p+i,4p+i) = P +1. When n = 4p + 2, since K4p+3,4p+3 c K2j4p+2j4p+2, from Lemma 2.1, we have p + 2 = 0(K4p+3,4p+3) < 0(K2j4p+2j4p+2). On the other hand, it is easy to see 0(K2,4p+2,4p+2) < 0(K2,4p+1,4p+i) + 1 = p + 2, so we have 0(K2,4p+2,4p+2) = p + 2. Summarizing the above, the theorem is obtained. □ 4 The thickness of K1,1,n,n Theorem 4.1. The thickness of the complete 4-partite graph K1i1in,n is "n + 3- 9(Ki,i,n,n) = 4 Proof. When n = 4p + 1, we can get a planar decomposition for Ki i 4p+i 4p+i from that of K2j4p+ij4p+i as follows. (1) When p = 0, Kiiijiji is a planar graph, 0(Kiiijiji) = 1. When p = 1,2 and 3, we join the vertex x1 to x2 in the last planar subgraph in the planar decomposition for K2i5,5, K2j9j9 and K2,i3,i3 which was shown in Figure 11, 12 and 13. Then we get the planar decomposition for Ki i 5 5, Ki i 9 9 and Ki i i3 i3 with 2, 3 and 4 planar subgraphs respectively. (2) When p > 4, we join the vertex x1 to x2 in Gp+1 in the planar decomposition for K2j4p+ij4p+i which was constructed in Lemma 3.1. The Gp+1 is shown in Figure 8 or 10 according to p is even or odd. Because x1 and x2 lie on the boundary of the same face, we will get a planar graph by adding edge xix2 to Gp+1. Then a planar decomposition for Kiiij4p+ij4p+i with p + 1 planar subgraphs can be obtained. Summarizing (1) and (2), we have Kiiij4p+ij4p+i < p +1. On the other hand, from Lemma 2.1, we have 0(K4p+1j4p+1) = p +1. Due to K4p+1,4p+1 c Ki , i, 4p,4p c Ki ,i,4p+i,4p+i, we get p + 1 < 0(Ki,ii4pi4p) < 0(Ki,ii4p+ii4p+i). So we have 0(Ki,ii4pi4p) = 0 ( Ki, i ,4p+i ,4p+i) = p +1. When n = 4p + 3, from Theorem 3.2 , we have 0(K2j4p+2j4p+2) = p + 2. Since K2,4p+2,4p+2 c K1,1,4p+2,4p+2 c K1,1,4p+3,4p+3 c K1,1,4(p+1),4(p+1), and the ideas from the previous case establish, we have p + 2 < 0(Kiiij4p+2i4p+2) < 0(Kiiii4p+3j4p+3) < 0(Kijij4(p+i)j4(p+i)) = p + 2, which shows 0(Kiiij4p+2i4p+2 ) = 0(Kiiii4p+3j4p+3) = p + 2. Summarizing the above, the theorem follows. □ X. Guo and Y. Yang: The thickness of Ki,„,„ and K2,n,n 131 References [1] V. B. Alekseev and V. S. Goncakov, The thickness of an arbitrary complete graph, Mat. Sb. (N. S.) 101(143) (1976), 212-230, http://mi.mathnet.ru/eng/msb3 8 9 7. [2] L. W. Beineke and F. Harary, The thickness of the complete graph, Canad. J. Math. 17 (1965), 850-859, doi:10.4153/cjm-1965-084-2. [3] L. W. Beineke, F. Harary and J. W. Moon, On the thickness of the complete bipartite graph, Math. Proc. Cambridge Philos. Soc. 60 (1964), 1-5, doi:10.1017/s0305004100037385. [4] Y. Chen and X. Yin, The thickness of the Cartesian product of two graphs, Canad. Math. Bull. 59 (2016), 705-720, doi:10.4153/cmb-2016-020-1. [5] M. Kleinert, Die Dicke des n-dimensionalen Wurfel-Graphen, J. Comb. Theory 3 (1967), 1015, doi:10.1016/s0021-9800(67)80010-3. [6] T. Poranen, A simulated annealing algorithm for determining the thickness of a graph, Inform. Sci. 172 (2005), 155-172, doi:10.1016/j.ins.2004.02.029. [7] W. T. Tutte, The thickness of a graph, Indag. Math. (Proceedings) 66 (1963), 567-577, doi: 10.1016/s1385-7258(63)50055-9. [8] J. M. Vasak, The Thickness of the Complete Graph, Ph.D. thesis, University of Illinois at Urbana-Champaign, ProQuest Dissertations Publishing, 1976, https://search. proquest.com/docview/302820090. [9] Y. Yang, A note on the thickness of Kl>m,n, Ars Combin. 117 (2014), 349-351. [10] Y. Yang, Remarks on the thickness of Kn>n,n, Ars Math. Contemp. 12 (2017), 135-144, doi: 10.26493/1855-3974.823.068.