/^creative ^commor
ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 14 (2018) 319-327 https://doi.org/10.26493/1855-3974.1349.b67
(Also available at http://amc-journal.eu)
The 4-girth-thickness of the complete graph
Christian Rubio-Montiel
UMILAFMIA 3175 CNRS at CINVESTAV-IPN, 07300, Mexico City, Mexico División de Matemáticas e Ingeniería, FES Ac-UNAM, 53150, Naulcalpan, Mexico
Received 10 March 2017, accepted 21 June 2017, published online 19 September 2017
Abstract
In this paper, we define the 4-girth-thickness 6(4, G) of a graph G as the minimum number of planar subgraphs of girth at least 4 whose union is G. We prove that the 4-girth-thickness of an arbitrary complete graph Kn, 6(4, Kn), is [np] for n = 6,10 and
6(4, K6) = 3.
Keywords: Thickness, planar decomposition, girth, complete graph. Math. Subj. Class.: 05C10
1 Introduction
A finite graph G is planar if it can be embedded in the plane without any two of its edges crossing. A planar graph of order n and girth g has size at most g—■ (n - 2) (see [6]), and an acyclic graph of order n has size at most n - 1, in this case, we define its girth as to. The thickness 6(G) of a graph G is the minimum number of planar subgraphs whose union is G; i.e. the minimum number of planar subgraphs into which the edges of G can be partitioned.
The thickness was introduced by Tutte [11] in 1963. Since then, exact results have been obtained when G is a complete graph [1, 3, 4], a complete multipartite graph [5, 12, 13] or a hypercube [9]. Also, some generalizations of the thickness for the complete graph Kn have been studied such that the outerthickness 6o, defined similarly but with outerplanar instead of planar [8], and the S-thickness 6S, considering the thickness on a surfaces S instead of the plane [2]. See also the survey [10].
We define the g-girth-thickness 6(g, G) of a graph G as the minimum number of planar subgraphs of girth at least g whose union is G. Note that the 3-girth-thickness 6(3, G) is the usual thickness and the TO-girth-thickness 6(to, G) is the arboricity number, i.e. the minimum number of acyclic subgraphs into which E(G) can be partitioned. In this paper, we obtain the 4-girth-thickness of an arbitrary complete graph of order n = 10.
E-mail address: christian@cs.cinvestav.mx (Christian Rubio-Montiel) ©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
320
Ars Math. Contemp. 14 (2018) 267-284
2 The exact value of 6(4, K„) for n = 10
Since the complete graph Kn has size and a planar graph of order n and girth at least 4 has size at most 2(n — 2) for n > 3 and n — 1 for n G {1,2} then the 4-girth-thickness of Kn is at least
n(n — 1)	
2(2n — 4)	
n + 1
1		n + 2
2n — 4		4
+
for n > 3 and also |"n+2"| for n G {1,2}, we have the following theorem.
Theorem 2.1. The 4-girth-thickness 0(4, Kn) of Kn equals	for n = 6,10 and
0(4, Ke) =3.
Proof. Figure 1 displays equality for n < 5.
i

2 , 2
4
2
Figure 1: 0(4, Kn) = f^] for n =1,2, 3,4,5.
To prove that 0(4, Ke) = 3 >	= 2, suppose that 0(4, Ke) = 2. This partition
define an edge coloring of Ke with two colors. By Ramsey's Theorem, some part contains a triangle obtaining a contradiction for the girth 4. Figure 2 shows a partition of Ke into tree planar subgraphs of girth at least 4.
Figure 2: 0(4, Ke) = 3.
For the remainder of this proof, we need to distinguish four cases, namely, when n = 4k — 1, n = 4k, n = 4k + 1 and n = 4k + 2 for k > 2. Note that in each case, the lower bound of the 4-girth thickness require at least k + 1 elements. To prove our theorem, we exhibit a decomposition of K4k into k +1 planar graphs of girth at least 4. The other three
C. Rubio-Montiel: The 4-girth-thickness of the complete graph
321
cases are based in this decomposition. The case of n = 4k - 1 follows because K4fc_i is a subgraph of K4k. For the case of n = 4k + 2, we add two vertices and some edges to the decomposition obtained in the case of n = 4k. The last case follows because K4fc+1 is a subgraph of K4fc+2. In the proof, all sums are taken modulo 2k.
1. Case n = 4k. It is well-known that a complete graph of even order contains a cyclic factorization of Hamiltonian paths, see [7]. Let G be a subgraph of K4k isomorphic to K2k. Label its vertex set V(G) as {vi; v2,..., v2k}. Let Fi be the Hamiltonian path with edges
V1V2, V2V2k, V2kV3, V3V2fc_l, . . . , V2 + fcVi+fc.
Let Fj be the Hamiltonian path with edges
vivi+i,vi+ivi-i,vi-ivi+2, Vj+2Vj-2, . . . , v¿+fc+ivi+fc, where i e {2,3,..., k}.
Such factorization of G is the partition {E(Fi), E(F2),..., E(Fk)}. We remark that the center of F¿ has the edge e = vj+ pk-j vj+ p 3k-j, see Figure 3.
a)

i + 1
M f1
+r t- i-i
v,+ r 32k
v,+r k i-i +r 21
v,+ r k
Vi+k+1
vi+k-1
b)
v, ^%i+1
vi+r3í i+1
v,+r k i-1 +r kk i
Mt i
vi+k-1
vi+k+1
Figure 3: The Hamiltonian path F^ Left a): The dashed edge e for k odd. Right b) The dashed edge e for k even.
Now, consider the complete subgraph G' of K4k such that G' = K4k \ V(G). Label its vertex set V(G') as {vl, v2,..., v2k} and consider the factorization, similarly as before, {E(F'), E(F2),..., E(Fk)} where F/ is the Hamiltonian path with edges
viv'+l, vi+lvi-l, vi-lv'+2, v'+2v'-2, . . . , vi+fc+lvi+fc, where i G {1,2,..., k}.
Next, we construct the planar subgraphs Gl, G2,...,Gk-l and Gk of girth 4, order 4k and size 8k - 4 (observe that 2(4k - 2) = 8k - 4), and also the matching Gk+l, as follows. Let Gj be a spanning subgraph of K4k with edges E(Fj) U E(F/) and

jv+i, vi+ivi_i, vi+ivi-i, vi-ivi+2, vi-ivi+2,...,vi+fc+ivi+fc, vj+fc+ivi+fc
v
v
322
Ars Math. Contemp. 14 (2018) 267-284
where i e {1,2,..., k}; and let Gk+1 be a perfect matching with edges vjvj for j e {1, 2,..., 2k}. Figure 4 shows Gj is a planar graph of girth at least 4.
b)
vi
V2
G
k+1
V2fc

Figure 4: Left a): The graph Gj for any i e {1, 2,..., k}. Right b) The graph Gk+1.
v
v
k + 1
To verify that K4k = |j G^ 1) If the edge v^ vi2 of G belongs to the factor Fj
i=1
then vjj vi2 belongs to Gj. If the edge is primed, belongs to Gj. 2) The edge v^ v-2 belongs to Gk+1 if and only if i1 = i2, otherwise it belongs to the same graph Gj as vj1 vj2. Similarly in the case of vvj2 and the result follows.
2.	Case n = 4k - 1. Since K4k-1 c K4k, we have
k +1 < 0(4, K4fc_1) < 0(4, K4fc) < k + 1.
3.	Case n = 4k + 2 (for k = 2). Let {G1,..., Gk+1} be the planar decomposition of K4k constructed in the Case 1. We will add the two new vertices x and y to every planar subgraph Gj, when 1 < i < k + 1, and we will add 4 edges to each Gj, when 1 < i < k, and 4k +1 edges to Gk+1 such that the resulting new subgraphs of K4k+2 will be planar. Note that (42kt + 4k + 4k + 1 = (4k+2t.
To begin with, we define the graph ffk+1 adding the vertices x and y to the planar subgraph Gk+1 and the 4k +1 edges
{xy,xv1,xv2,xv3,xv4,... ,xv2k_1,xv2k, yv'x,yv2,yv3,yv4,..., yv2k_1,yv2k}. The graph Hk+1 has girth 4, see Figure 5.
In the following, for 1 < i < k, by adding vertices x and y to Gj and adding 4 edges to Gj, we will get a new planar graph Hj such that {H1,..., Hk+1} is a planar decomposition of K4k+2 such that the girth of every element is 4. To achieve it, the given edges to the graph Hj will be vjx, xvj_1,vjy, yvj_1, for some odd
j e {1, 3,..., 2k - 1}.
According to the parity of k, we have two cases:
C. Rubio-Montiel: The 4-girth-thickness of the complete graph
323
Figure 5: The graph Hk+1.
•	Suppose k odd. For odd i G {1, 2,..., k}, we define the graph Hi adding the vertices x and y to the planar subgraph Gi and the 4 edges
{xvi+ [f] -1, xvi+ [32k 1 , yvi+ \32k 1-1' yvi+ [21 }
when is even, otherwise
{y<+r f 1-1'yVi+[ 32k 1 'XM 32k 1-1'XVI+[ f 1}.
Additionally, for even i G {1, 2,..., k}, we define the graph Hi adding the vertices x and y to the planar subgraph Gi and the 4 edges
{xvi+r 11-1, xvi+r 11, yvi+ r t1-1, yvi+ r 11}
when is even, otherwise
{yvi+rk 1-1,yvi+r 11 ,xvi+r 11-1 ,xvi+r 11}.
Note that the graph Hi has girth 4 for all i, see Figure 6.
•	Suppose k even. Similarly that the previous case, for odd i G {1,2,..., k}, we define the graph Hi adding the vertices x and y to the planar subgraph Gi and
the 4 edges
{xvi+r 32k 1+1, xvi+ r f 1, yvi+ r f 1+1, yv r 32k 1}
when is even, otherwise
{yvi+ r 32k 1+1, yvi+ r 3^ 1, xvi+r t 1+1, xvi+ r 32k 1}.
On the other hand, for even i G {1, 2,..., k}, we define the graph Hi adding the vertices x and y to the planar subgraph Gi and the 4 edges
{xvi+r 11, xvi+ r 11 -1, yvi+ r 11, yv*+r k 1 -1}
when is even, otherwise
{yvi+rk 1, yvI+r 11-1, xvi+r 11, xv r 11 -1}.
Note that the graph Hi has girth 4 for all i, see Figure 7.
324
Ars Math. Contemp. 14 (2018) 267-284
a)
Vk+i
k+i
Vk+i
k+i
vx
Vi+\k 1-1
•Vi+r 11
v,-+r 3k
W^Vi + k Vi+k+1
Vi+k-1
V. _«Vi + 1
Vi+r 11-1
•M 11
V,-+r 3k
•r^^Vi+k
Vi+k+1
Vi+k-1
V
V
Figure 6: The graph H when k is odd and its auxiliary graph F*. Above a) When i is odd. Botton b) When i is even.
C. Rubio-Montiel: The 4-girth-thickness of the complete graph	325
a)
Vk + i
k + i
b)
Vk + i
k+i
vx
»M k
i+ k -i
v,+\ -k l+i
»M k i
M * i

vi+k-1
Vi+k+1 V,	J'i + l

»M k
i+ k -i
Vi+\3k l+i
»M k i
Vi+\ ¥ l
Vi+k+l
vi+k-1
V
V
Figure 7: The graph H when k is even and its auxiliary graph F*. Above a) When i is odd. Botton b) When i is even.
326
Ars Math. Contemp. 14 (2018) 267-284
In order to verify that each edge of the set
[xv'l,xv2,xv'3,XV3,. .. ,xv2k_1;xv2k,yvi,yv'2,yv3,yv's,. .. ,yv2k-i,yv'^k}.
is in exactly one subgraph Hi, for i e {1,..., k}, we obtain the unicyclic graph F* identifying vj and vj resulting in vj; identifying x and y resulting in a vertex which is contracted with one of its neighbours. The resulting edge, in dashed, is showed in Figures 6 and 7. The set of those edges are a perfect matching of K2k proving that the added two paths of length 2 in Gi have end vertices vj and vj_1, and the other vj and vj_1. The election of the label of the center vertex is such that one path is
vevenxv
odd and vevenyvodd and the result follows.
4. Case n = 4k + 1 (for k = 2). Since K4k+1 c K4k+2, we have k +1 < 0(4, K4k+i) < 0(4, K4k+2) < k + 1.
For k = 2, Figure 8 displays a decomposition of three planar graphs of girth at least 4 proving that 0(4, Kg) = [^] = 3.
By the four cases, the theorem follows.	□
About the case of K10, it follows 3 < 0(4, K10) < 4. We conjecture that 0(4, K10) =
4.
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, Minimal decompositions of complete graphs into subgraphs with embeddability properties, Canad. J. Math. 21 (1969), 992-1000, doi:10.4153/cjm-1969-109-4.
[3]	L. W. Beineke and F. Harary, On the thickness of the complete graph, Bull. Amer. Math. Soc. 70 (1964), 618-620, doi:10.1090/s0002-9904-1964-11213-1.
[4]	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.
[5]	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.
[6]	J. A. Bondy and U. S. R. Murty, Graph Theory, volume 244 of Graduate Texts in Mathematics, Springer, New York, 2008, doi:10.1007/978-1-84628-970-5.
C. Rubio-Montiel: The 4-girth-thickness of the complete graph
327
[7]	G. Chartrand and P. Zhang, Chromatic Graph Theory, Discrete Mathematics and its Applications, CRC Press, Boca Raton, Florida, 2009.
[8]	R. K. Guy and R. J. Nowakowski, The outerthickness & outercoarseness of graphs, I. The complete graph & the n-cube, in: R. Bodendiek and R. Henn (eds.), Topics in Combinatorics and Graph Theory, Physica-Verlag, Heidelberg, pp. 297-310, 1990, doi:10.1007/ 978-3-642-46908-4_34, essays in honour of Gerhard Ringel, papers from the Graph Theory Meeting held in Oberwolfach, June 3-9, 1990.
[9]	M. Kleinert, Die Dicke des n-dimensionalen Wurfel-Graphen, J. Comb. Theory 3 (1967), 1015, doi:10.1016/s0021-9800(67)80010-3.
[10]	P. Mutzel, T. Odenthal and M. Scharbrodt, The thickness of graphs: a survey, Graphs Combin. 14 (1998), 59-73, doi:10.1007/pl00007219.
[11]	W. T. Tutte, The thickness of a graph, Indag. Math. (Proceedings) 66 (1963), 567-577, doi: 10.1016/s1385-7258(63)50055-9.
[12]	Y. Yang, A note on the thickness of K;,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, https://amc-journal.eu/index.php/amc/article/view/82 3.