¿^creative	, ars mathematica
^commons	contemporánea
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 12 (2017) 135-144
Remarks on the thickness of Kn,n,n
Yan Yang *
Department of Mathematics, Tianjin University, Tianjin, P.R.China Received 10 March 2015, accepted 14 March 2016, published online 3 November 2016
Abstract
The thickness 6(G) of a graph G is the minimum number of planar subgraphs into which G can be decomposed. In this paper, we provide a new upper bound for the thickness of the complete tripartite graphs Kn n n (n > 3) and obtain 6(Kn n n) = , when n = 3 (mod 6).
Keywords: Thickness, complete tripartite graph, planar subgraphs decomposition. Math. Subj. Class.: 05C10
1 Introduction
The thickness 6(G) of a graph G is the minimum number of planar subgraphs into which G can be decomposed. It was defined by Tutte [11] in 1963, derived from early work on biplanar graphs [2, 10]. It is a classical topological invariant of a graph and also has many applications to VLSI design, graph drawing, etc. Determining the thickness of a graph is NP-hard [7], so the results about thickness are few. The only types of graphs whose thicknesses have been determined are complete graphs [1,3], complete bipartite graphs [4] and hypercubes [5]. The reader is referred to [6, 8] for more background on the thickness problems.
In this paper, we study the thickness of complete tripartite graphs Kn,n,n, (n > 3). When n = 1,2, it is easy to see that K1,1,1 and KC2,2,2 are planar graphs, so the thickness of both ones is one. Poranen proved 6(Kn,n,n) < [f] in [9] which was the only result about the thickness of Kn,n,n, as far as the author knows. We will give a new upper bound for 6(Kn,n,n) and provide the exact number for the thickness of Kn,n,n, when n is congruent to 3 mod 6, the main results of this paper are the following theorems.
Theorem 1.1. For n > 3, 6(Kn,n,n) < [^2 + 1.
Theorem 1.2. 6(K„,„,„) = [^2 when n = 3 (mod 6).
* Supported by the National Natural Science Foundation of China under Grant No. 11401430 E-mail address: yanyang@tju.edu.cn (Yan Yang)
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
136
Ars Math. Contemp. 12 (2017) 111-126
2 The proofs of the theorems
In [4], Beineke, Harary and Moon determined the thickness of complete bipartite graph Km,n for almost all values of m and n.
Lemma 2.1. [4] The thickness of Km,n is |~2(m+w-2)l except possibly when m and n are odd, m < n and there exists an integer k satisfying n = L2^^—"].
Lemma 2.2. For n > 3, 0(Kn,n,n) > [].
Proof. Since K„,2„ is a subgraph of K„,„,„, we have 0(Kn,n,n) > 6(Kn,2„). From Lemma 2.1, the thickness of Kn,2n (n > 3) is [n^1], so the lemma follows.	□
For the complete tripartite graph Kn,n,n with the vertex partition (A, B, C), where
A = {ao,..., an-1}, B = {bo,..., bn-i} and C = {c0,..., Cn-i}, we define a type of graphs, they are planar spanning subgraphs of Kn n n, denoted by G[ aibj+iCk+i], in which 0 < i,j,k < n - 1 and all subscripts are taken modulo n. The graph G[ aibj+iCk+i] consists of n triangles aibj+iCk+i for 0 < i < n - 1 and six paths of length n - 1, they are
aobj+iCfc+2a3bj+4Cfc+5 . .. a3ibj+3i+iCk+3i+2 . ..,
cka1bj+2Ck+3a4bj+5 . . . Ck+3ia3i+1bj+3i+2 . . . , bjCk+ia2bj+3Ck+4a5 . .. bj+3iCk+3i+ia3i+2 . ..,
aoCk+ibj+2a3Ck+4bj+5 . .. a3iCk+3i+ibj+3i+2 . .., bjaiCk+2bj+3a4Ck+5 . .. bj+3ia3i+iCk+3i+2 . .., Ckbj+ia2Ck+3bj+4a5 . . . Ck+3ibj+3i+ia3i+2 . . . .
Equivalently, the graph G[aibj+iCk+i] is the graph with the same vertex set as Kn,n,n and edge set
{aibj+i-i, aibj+i, aibj+i+i, aiCk+i-i, aiCk+i, aiCk+i+i | 1 < i < n - 2} U{bj+iCk+i-i, bj+iCk+i, bj+iCk+i+i | 1 < i < n - 2} U{aobj, aobj+i, an-ibj+n-2, an-ibj+n-i} U{aoCk ,aoCk+i, an-iCk+n-2 , ar—iCk+n-i)}
U{bj Ck ,bj Ck + i,bj+n-iCk+n-2,bj+n-iCk+n-i}. Figure 1(a) illustrates the planar spanning subgraph G[aibiCi] of K5 5 5.
Y. Yang: Remarks on the thickness of K„,„,„	137
Figure 1: A planar subgraphs decomposition of K5j5j5
Theorem 2.3. When n = 3p + 2 (p is a positive integer), #(Kni„in) < p + 2.
Proof. When n = 3p + 2 (p is a positive integer), we will construct two different planar subgraphs decompositions of Kn n n according to p is odd or even, in which the number of planar subgraphs is p + 2 in both cases.
Case 1. p is odd. Let Gi,..., Gp be p planar subgraphs of K„,„in where
Gt = G[aibi+3(i-1)ci+6(i-1)L for 1 < t < ; and Gi =	— 1)ci+6(t—1)+2],
for ^i3 < t < p and p > 3. From the structure of G[ajbj+ick+i], we get that no two edges in G1,..., Gp are repeated. Because subscripts in Gt, 1 < t < p are taken modulo n, {3(t - 1) (mod n) | 1 < t < p} = {0, 3,6,..., 3(p - 1)}, {6(t - l) (modn) | 1 < t < pt-1 } = {0,6,..., 3(p -1)} and {6(t - 1) + 2 (modn) | < t < p} = {3, 9,..., 3(p -2)}, the subscript sets of b and c in Gt, 1 < t < p are the same, i.e.,
138
Ars Math. Contemp. 12 (2017) 111-126
{i + 3(t - 1) (mod n) | 1 < t < p} = {i + 6(t - 1) (mod n) | 1 < t < ^y1} U {i + 6(t - 1) + 2 (modn) | < t < p}.
Furthermore, if there exists t G {1,... ,p} such that ajbj is an edge in Gt, then ajCj is an edge in Gk for some k G {1,... ,p}. If the edge ajbj is not in any Gt, then neither is the edge ajCj in any Gt, for 1 < t < p.
From the construction of Gt, the edges that belong to Kn n n but not to any Gt, 1 <
t < p, are
aob3(t-i)-i, aoC3(t_i)_i, 1 < t < p	(1)
an-1&3(t-1), an_lC3(i-1), 1 < t < p	(2)
aA-3, ajbi-2, 0 < i < n - 1	(3)
ajCj-3, ajCj-2, 0 < i < n - 1	(4)
p + 3
bjCj+3(t-i)-i, bjci+3(i-i), 0 < i < n - 1 and t = ——	(5)
b3(t-1)C6(t-1)-1, b3(t-i)-iC6(t-i), 1 < t <	(6)
p + 3
^(i-i^i-i^^ b3(i-1)-1C6(i-1) + 2, —< t < p andp > 3	(7)
Let Gp+ i be the graph whose edge set consists of the edges in (3) and (5), and Gp+2 be the graph whose edge set consists of the edges in (1), (2), (4), (6) and (7). In the following, we will describe plane drawings of Gp+1 and Gp+2.
(a)	A planar embedding of Gp+1.
Place vertices b0, b1,..., bn-1 on a circle, place vertices ai+3 and cj+ n+i in the middle of b and bj+1, join each of aj+3 and ci+ n+i to both bj and bj+1, we get a planar embedding of Gp+1. For example, when p = 1, n = 5, Figure 1(b) shows the subgraph G2 of K5j5j5.
(b)	A planar embedding of Gp+2.
Firstly, we place vertices c0 , c1 ,..., cn-1 on a circle, join vertex ai+3 to cj and ci+1, for
0	< i < n - 1 , so that we get a cycle of length 2n. Secondly, join vertex an-1 to c3(t-1) for 1 < t < p, with lines inside of the cycle. Let ^ be the line drawn inside the cycle joining an-1 with c6(t-1)-1 if 1 < t < or with c6(t-1)+1 if < t < p (p > 3). For
1	< t < p, insert the vertex b3(t-1) in the line Thirdly, join vertex a0 to c3(t-1)-1 for 1 < t < p, with lines outside of the cycle. Let 4 be the line drawn outside the cycle joining ao with c6(t-1) if 1 < t < P+1 or with c6(i-1)+2 if P+3 < t < p (p > 3). For 1 < t < p, insert the vertex b3(t-1)-1 in the line In this way, we can get a planar embedding of Gp+2. For example, when p = 1, n = 5, Figure 1(c) shows the subgraph G3 of K5,5,5.
Summarizing, when p is an odd positive integer and n = 3p+2, we get a decomposition of Kn n n into p + 2 planar subgraphs G1,..., Gp+2.
Case 2. p is even. Let G1,..., Gp be p planar subgraphs of K„,„in where
Gt = G[ajbj+3(i-1)ci+6(i-1)+3],for 1 < t < p;and Gt = G[aibj+3(t-1)ci+6(i-1) + 2],for
< t < p. With a similar argument to the proof of Case 1, we can get that the subscript sets of b and c in Gt, 1 < t < p are the same, i.e.,
{i + 3(t - 1) (modn) | 1 < t < p}
= {i + 6(t - 1) + 3 (modn) | 1 < t < p} U {i + 6(t - 1) +2 (modn) | ^y2- < t < p}.
Y. Yang: Remarks on the thickness of K„,„,„	139
From the construction of Gt, Gp and G p+2 have n - 2 edges in common, they are
bi+3(p+2_1)Ci+6(p+2_!)+1, 1 < i < n - 1 and i = n - 4, we can delete them in one of thes2e two graphs2 to avoid repetition.
The edges that belong to K„in,m but not to any Gt, 1 < t < p, are
a0b3(t_1)_1, a0C3(i_1)_1? 1 < t < P	(8)
a„_i63(t_i), a„_1C3(t_1), 1 < t < p	(9)
aj6j_3, aj6j_2, 0 < i < n — 1 aiCj_3, ajCj_2, 0 < i < n — 1 bjCj_1, bjCj, bjCi+1, 0 < i < n - 1
p
b3(i_1)C6i_4, 1 < t < 2
P + 2
»3(i_1)C6i_5, —^ <t < p
p
b3(i_1)_1C6i_3, 1 < t < 2
p+2
»3(i_1)_1 C6t_4, ~ < t < p
10) 11) 12)
13)
14)
15)
16)
Let Gp+ 1 be the graph whose edge set consists of the edges in (10), (11) and (12), and Gp+2 be the graph whose edge set consists of the edges in (8), (9), (13), (14), (15) and (16). We draw Gp+1 in the following way. Firstly, place vertices b0, c0, b1, C1,..., bn_1, Cn_1 on a circle C, join vertex Cj to b and bj+1, we get a cycle of length 2n. Secondly, place vertices a0,a2,...,an_2 on a circle C' in the unbounded region defined by the circle C such that C is contained in the closed disk defined by C', place vertices a1, a3,..., a„_1 on a circle C" contained in the bounded region of C. Join a to bj_3, bj_2, Cj_3, and Cj_2, join bj to cj+1. We can get a planar embedding of Gp+1, so it is a planar graph. Gp+2 is also planar because it is a subgraph of a graph homeomorphic to a dipole (two vertices joined by some edges). For example, when p = 2, n = 8, Figure 2(c) and Figure 2(d) show the subgraphs G3 and G4 of K8j8j8 respectively.
Summarizing, when p is an even positive integer and n = 3p + 2, we obtain a decomposition of K„ini„ into p + 2 planar subgraphs G1,..., Gp+2.
Theorem follows from Cases 1 and 2.	□
From the proof of Theorem 2.3, we draw planar subgraphs decompositions of K5 5 5 and K8 8 8 as illustrated in Figure 1 and Figure 2 respectively.
140	Ars Math. Contemp. 12 (2017) 111-126
(b) The subgraph G2 - b4c0 - b5c\ - b6c2 - b0c4 - b1c5 — b2c6 of K8,in which
G2 = G[ajbi+3cj]
Y. Yang: Remarks on the thickness of K„,„,„	141
(c) The subgraph G3 of K8,8,8	(d) The subgraph G4 of K8,8,8
Figure 2: A planar subgraphs decomposition of K8,8,8
Proof of Theorem 1.1. Because graph K„-i„-in-i is a subgraph of Kn n n,
— 1, n— 1, n— i) < ^(Kn, n , n), by Theorem 2.3, 0(Kn , n , n) < p + 2 also holds, when n = 3p or n = 3p +1 (p is a positive integer), the theorem follows.	□
Proof of Theorem 1.2. When n = 3p is odd, i.e., n = 3 (mod 6), we decompose Kn,n,n into p + 1 planar subgraphs G1,..., Gp+1, where Gt = G[a,jbi+3(i—1)ci+6(i—1)], for 1 < t < p. With a similar argument to the proof of Theorem 2.3, we can get that the subscript sets of b and c in Gt, 1 < t < p are the same, i.e.,
{i + 3(t - 1) (modn) | 1 < t < p} = {i + 6(t - 1) (modn) | 1 < t < p}.
If the edge ajbj is in Gt for some t G {1,... ,p}, then there exists k G {1,... ,p} such that ajCj is in Gk. If the edge ajbj is not in any Gt, then neither is the edge ajCj in any Gt, for
1 < t < p .
From the construction of Gt = G[ajbi+3(t—1)ci+6(t—1)], we list the edges that belong
to Kn,n,n but not to any Gt, 1 < t < p, as follows.
aob3(i— i)—1, aoC6(t—i)—i, 1 < t < p	(17)
On— lb3(t— 1), an— lC6(t— 1), 1 < t < p	(18)
b3(t—1)C6(t—i)—1, b3(t—1)—1 C6(t—1), 1 < t < p	(19)
Let Gp+1 be the graph whose edge set consists of the edges in (17), (18) and (19). It is easy to see that Gp+1 is homeomorphic to a dipole and it is a planar graph.
Summarizing, when p is an odd positive integer and n = 3p, we obtain a decomposition of Kn,n,n into p +1 planar subgraphs G1,..., Gp+1, therefor 0(Kn,n,n) < p + 1. Combining this fact and Lemma 2.2, the theorem follows.	□
142
Ars Math. Contemp. 12 (2017) 111-126
(a) The subgraph G1 = G[abjCj] of K333
(b) The subgraph G2 of K3 3 3
Figure 3: A planar subgraphs decomposition of K333
According to the proof of Theorem 1.2, we draw a planar subgraphs decomposition of K3, 3 , 3 as shown in Figure 3.
For some other 6(Kn,n,n) with small n, combining Lemma 2.2 and Poranen's result mentioned in Section 1, we have #(K4j4j4) = 2, 0(K6j6j6) = 3. Since there exists a decomposition of K7 7 7 with three planar subgraphs as shown in Figure 4, Lemma 2.2 implies that 6(K7,7,7) = 3. We also conjecture that the thickness of Kn,n,n is	for
all n 3.	3
(a) The subgraph Gi = G^Acj] of K7,7,7
b
4
Y. Yang: Remarks on the thickness of K„,„,„	143
G2 - ai&2 - a263 - «364 - a4b5 - a5b6 - boci - b1c2 - b^c^ - b4C5 - b5c6 of K7,7,7 in
which G2 = G[ajbi+2ci+4j
Figure 4: A planar subgraphs decomposition of K7 7 7
144
Ars Math. Contemp. 12 (2017) 111-126
Acknowledgements
The author is grateful to the anonymous referees for many helpful comments and suggestions.
References
[1]	V. Alekseev and V. Goncakov, The thickness of an arbitrary complete graph., Math. USSR, Sb. 30 (1978), 187-202, doi:10.1070/SM1976v030n02ABEH002267.
[2]	J. Battle, F. Harary and Y. Kodama, Every planar graph with nine points has a nonplanar complement., Bull. Am. Math. Soc. 68 (1962), 569-571, doi:10.1090/S0002-9904-1962-10850-7.
[3]	L. W. Beineke and F. Harary, The thickness of the complete graph, Canad. J. Math 17 (1965), 6l8-620.
[4]	L. W. Beineke, F. Harary and J. W. Moon, On the thickness of the complete bipartite graph, in: Mathematical Proceedings of the Cambridge Philosophical Society, Cambridge Univ Press, volume 60, 1964 pp. 01-05.
[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]	E. Makinen and T. Poranen, An annotated bibliography on the thickness, outerthickness, and arboricity of a graph., Missouri J. Math. Sci. 24 (2012), 76-87.
[7]	A. Mansfield, Determining the thickness of graphs is NP-hard., Math. Proc. Camb. Philos. Soc. 93 (1983), 9-23, doi:10.1017/S030500410006028X.
[8]	P. Mutzel, T. Odenthal and M. Scharbrodt, The thickness of graphs: a survey, Graphs and combinatorics 14 (1998), 59-73.
[9]	T. Poranen, A simulated annealing algorithm for determining the thickness of a graph., Inf. Sci. 172 (2005), 155-172, doi:10.1016/j.ins.2004.02.029.
[10]	W. Tutte, The non-biplanar character of the complete 9-graph., Can. Math. Bull. 6 (1963), 319-339, doi:10.4153/CMB-1963-026-x.
[11]	W. Tutte, The thickness of a graph, in: Indagationes Mathematicae (Proceedings), Elsevier, volume 66, 1963 pp. 567-577.