¿^creative	, ars mathematica
^commons	contemporánea
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 16 (2019) 19-24
https://doi.org/10.26493/1855-3974.1488.182
(Also available at http://amc-journal.eu)
A note on the 4-girth-thickness of K
*
n,n,n
Xia Guo, Yan Yang t
School of Mathematics, Tianjin University, Tianjin, P. R. China
Received 20 September 2017, accepted 8 January 2018, published online 24 August 2018 Abstract
The 4-girth-thickness 6(4, G) of a graph G is the minimum number of planar subgraphs of girth at least four whose union is G. In this paper, we obtain that the 4-girth-thickness of complete tripartite graph Kn,n,n is [n^] except for 6(4, K 1,1,1) = 2. And we also show that the 4-girth-thickness of the complete graph K10 is three which disprove the conjecture posed by Rubio-Montiel concerning to 6(4, K10).
Keywords: Thickness, 4-girth-thickness, complete tripartite 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 defined by W. T. Tutte [10] in 1963. Then, the thicknesses of some graphs have been obtained when the graphs are hypercube [7], complete graph [1, 2, 11], complete bipartite graph [3] and some complete multipartite graphs [6, 12, 13].
In 2017, Rubio-Montiel [9] defined the g-girth-thickness 6(g, G) of a graph G as the minimum number of planar subgraphs whose union is G with the girth of each subgraph is at least g. It is a generalization of the usual thickness in which the 3-girth-thickness 6(3, G) is the usual thickness 6(G). He also determined the 4-girth-thickness of the complete graph Kn except K10 and he conjectured that 6(4, K10) = 4. Let Kn,n,n denote a complete tripartite graph in which each part contains n (n > 1) vertices. In [13], Yang obtained 6(Kn,n,n) = I"] when n = 3 (mod 6).
In this paper, we determine 6(4, Kn,n,n) for all values of n and we also give a decomposition of K10 with three planar subgraphs of girth at least four, which shows 6(4, K10) = 3.
* Supported by the National Natural Science Foundation of China under Grant No. 11401430.
1 Corresponding author.
E-mail addresses: guoxia@tju.edu.cn (Xia Guo), yanyang@tju.edu.cn (Yan Yang)
©® This work is licensed under https://creativecommons.Org/licenses/by/4.0/
20
ArsMath. Contemp. 16(2019) 19-24
2 The 4-girth-thickness of Kn,n,n
Lemma 2.1 ([4]). A planar graph with n vertices and girth g has at most (n — 2) edges.
Theorem 2.2. The 4-girth-thickness of Kn,n,n is
0(4, K„,„,„) = [^ except for 0(4, K^^) = 2.
Proof. It is trivial for n =1, 0(4, K1,1,1) = 2. When n > 1, because |E(Kn,n,n)| = 3n2, |V (Kn,n,n)| = 3n, from Lemma 2.1, we have
0(4, Kw) >
r 3n2	
2(3n — 2)	
n1
+ 77 +
		|~n + 1
2)		2
In the following, we give a decomposition of Kn,n,n into [ny1] planar subgraphs of girth at least four to complete the proof. Let the vertex partition of Kn,n,n be (U, V, W), where U = {u1,..., un}, V = {v1,..., vn} and W = {w1,..., wn}. In this proof, all the subscripts of vertices are taken modulo 2p.
Case 1: When n = 2p (p > 1). Let G1,..., Gp+1 be the graphs whose edge set is empty and vertex set is the same as V(K2p,2p,2p).
Step 1: For each Gj (1 < i < p), arrange all the vertices u1, v3_2j, u2, v4_2j, u3, v5_2j, ..., u2p, v2p_2j+2 on a circle and join uj to vj+2_2j and vj+1_2j, 1 < j < 2p. Then we get a cycle of length 4p, denote it by G1 (1 < i < p).
Step 2: For each G1 (1 < i < p), place the vertex w2i-1 inside the cycle and join it to u1,..., u2p, place the vertex w2j outside the cycle and join it to v1,..., v2p. Then we get a planar graph G2 (1 < i < p).
Step 3: For each G2 (1 < i < p), place vertices w2j for 1 < j < p and j = i, inside of the quadrilateral w2i-1 M2i_1v1M2i and join each of them to vertices M2i_1 and u2j. Place vertices w2j-_1, for 1 < j < p and j = i, inside of the quadrilateral w2iv2i_1Mfcv2j, in which uk is some vertex from U. Join each of them to vertices v2i-1 and v2j. Then we get a planar graph Gj (1 < i < p).
Step 4: For Gp+1, join w2i-1 to both v2j_1 and v2j, join w2j to both u2j_1 and u2j, for 1 < i < p, then we get a planar graph Gp+1.
For G1 U • • • U Gp+1 = Kn,n,n, and the girth of Gj (1 < i < p +1) is at least four, we obtain a 4-girth planar decomposition of K2p 2p 2p with p +1 planar subgraphs. Figure 1 shows a 4-girth planar decomposition of K4 4 4 with three planar subgraphs.
Case 2: When n = 2p + 1 (p > 1). Base on the 4-girth planar decomposition {G1,..., Gp+1} of K2p,2p,2p, by adding vertices and edges to each Gj (1 < i < p + 1) and some other modifications on it, we will get a 4-girth planar decomposition of K2p+1,2p+1,2p+1 with p + 1 subgraphs.
Step 1: (Add u to Gj, 1 < i < p.) For each Gj (1 < i < p), we notice that the order of the p — 1 interior vertices w2j, 1 < j < p, and j = i in the quadrilateral
2
n
X. Guo and Y. Yang: A note on the 4-girth-thickness of Kn,n,n
21
u2-V 2-u 3-V 3-u 4-xJ 4
(a) The graph G1.
(b) The graph G2.
(c) The graph G3. Figure 1: A 4-girth planar decomposition of K4 4 4.
4
w2i-iM2i-iviM2i of Gj has no effect on the planarity of Gj. We adjust the order of them, such that w2j_1M2j_1w2p_2j+2M2j is a face of a plane embedding of Gj. Place the vertex u in this face and join it to both w2j-1 and w2p_2j+2. We denote the planar graph we obtain
by Gj (1 < i < p).
Step 2: (Add v and w to G?1.) Delete the edge v1u2 in G?1, put both v and w in the face wku1v1wtv2u2 in which wk is some vertex from {w2j- | 1 < j < p} and wt is some vertex from {w2j_1 | 1 < j < p}. Join v to w, join v to u1, u2, and join w to v1, v2, we get a planar graph G1.
Step 3: (Add v and w to G?j, 2 < i < p.) For each Gj (2 < i < p), place the vertex v in the face wku2j_1v1u2j in which wk is some vertex from {w2j- | 1 < j < p and j = i}, and join it to u2j-1 and u2j. Place the vertex w in the face wkv2j_1uiv2j in which wk is some vertex from {w2j_1 | 1 < j < p and j = i} and ut is some vertex from U. Join w to both v2j-1 and v2j, we get a planar graph Gj (2 < i < p).
Step 4: (Add u, v and w to Gp+1.) We add u, v and w to Gp+1. For 1 < i < 2p, join u to each vj, join v to each wj, join w to each uj, join u to both v and w, and join v1 to u2, then we get a planar graph Gp+1. Figure 2 shows a plane embedding of Gp+1.
For G1 U • • • U Gp+1 = K„)Bi„, and the girth of Gj (1 < i < p +1) is at least four, we obtain a 4-girth planar decomposition of K2p+1j2p+1j2p+1 with p + 1 planar subgraphs. Figure 3 shows a 4-girth planar decomposition of K5 5 5 with three planar subgraphs.
Case 3: When n = 3, Figure 4 shows a 4-girth planar decomposition of K3 3 3 with two planar subgraphs.
Summarizing the above, the theorem is obtained.
□
22
ArsMath. Contemp. 16(2019) 19-24
v
Figure 2: The graph Gp+1.
Figure 3: A 4-girth planar decomposition of K5j5j5.
Figure 4: A 4-girth planar decomposition of K3 3 3.
X. Guo and Y. Yang: A note on the 4-girth-thickness of Kn
23
3 The 4-girth-thickness of K10
In [9], the author posed the question whether 6(4, K10) = 3 or 4, and conjectured that it is four. We disprove his conjecture by showing 6(4, Kw) = 3.
Theorem 3.1. The 4-girth-thickness of K10 is three.
Proof. From [9], we have 0(4, K10) > 3. We draw a 4-girth planar decomposition of Kio with three planar subgraphs in Figure 5, which shows 0(4, K10) < 3. The theorem
We would like to state that after submitting this paper for review, we notice that there exist two results regarding the 4-girth-thickness of K2p,2p,2p and K10. Rubio-Montiel [8] obtained the exact value of the 4-girth-thickness of the complete multipartite graph when each part has an even number of vertices. And by computer, Castaneda-Lopez et al. [5] found the other two decompositions of K10 into three planar subgraphs of girth at least four. In this paper, we give these results in a constructive way.
References
[1]	V. B. Alekseev and V. S. Goncakov, The thickness of an arbitrary complete graph, Math. USSRSbornik 30 (1976), 187-202, http://stacks.iop.org/0025-57 34/30/i=2/ a=A0 4.
[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]	J. A. Bondy and U. S. R. Murty, Graph Theory, volume 244 of Graduate Texts in Mathematics, Springer-Verlag, London, 2008, doi:10.1007/978-1-84628-970-5.
[5]	H. Castaneda-L6pez, P. C. Palomino, A. B. Ramos-Tort, C. Rubio-Montiel and C. Silva-Ruiz, The 6-girth-thickness of the complete graph, 2017, arXiv:170 9.07 4 66 [math.CO].
[6]	Y. C. Chen and Y. Yang, The thickness of the complete multipartite graphs and the join of graphs, J. Comb. Optim. 34 (2017), 194-202, doi:10.1007/s10878-016-0057-1.
[7]	M. Kleinert, Die dicke des n-dimensionalen Wurfel-graphen, J. Comb. Theory 3 (1967), 10-15, doi:10.1016/s0021-9800(67)80010-3.
[8]	C. Rubio-Montiel, The 4-girth-thickness of the complete multipartite graph, 2017, arXiv:1709.03932 [math.CO].
Figure 5: A 4-girth planar decomposition of Kw.
follows.
□
24	Ars Math. Contemp. 16 (2019) 157-171
[9] C. Rubio-Montiel, The 4-girth-thickness of the complete graph, ArsMath. Contemp. 14 (2018), 319-327, doi:10.26493/1855-3974.1349.b67.
[10]	W. T. Tutte, The thickness of a graph, Indag. Math. (Proceedings) 66 (1963), 567-577, doi: 10.1016/s1385-7258(63)50055-9.
[11]	J. M. Vasak, The thickness of the complete graph, Notices Amer. Math. Soc. 23 (1976), A-479.
[12]	Y. Yang, A note on the thickness of Ki,m,n, Ars Combin. 117 (2014), 349-351.
[13]	Y. Yang, Remarks on the thickness of Kn>n,n, Ars Math. Contemp. 12 (2017), 135-144, doi: 10.26493/1855-3974.823.068.