ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 8 (2015) 409-416
Strongly light subgraphs in the 1-planar graphs with minimum degree 7
A graph is 1-planar if it can be drawn in the plane such that every edge crosses at most one other edge. A connected graph H is strongly light in a family of graphs G, if there exists a constant A, such that every graph G in G contains a subgraph K isomorphic to H with degG (v) < A for all v e V(K). In this paper, we present some strongly light subgraphs in the family of 1-planar graphs with minimum degree 7.
Keywords: Strongly light subgraph, 1-planar graph. Math. Subj. Class.: 05C10
1 Introduction
All graphs considered are finite, simple and undirected unless otherwise stated. We denote by V(G) and E(G) the vertex set and the edge set of G. We shall denote by F(G) the set of faces of an embedded graph G. The degree of a vertex v in G, denoted by degG(v), is the number of edges of G incident with v. We denote the minimum and maximum degrees of vertices in G by 8(G) and A(G), respectively. A wheel Wn is a graph obtained by taking the join of a cycle Cn and a single vertex. In an embedded graph G, the degree of a face f, denoted by degG(f), is the number of edges with which it is incident, each cut edge being counted twice. A k-vertex, k+-vertex and k--vertex is a vertex of degree k, at least k and at most k, respectively. Similarly, we can define k-face, k+-face and k- -face.
A graph is 1-embeddable in a surface S if it can be drawn in S such that every edge crosses at most one other edge. In particular, a graph is 1-planar if it can be drawn in
E-mail address: wangtao@henu.edu.cn (Tao Wang)
Tao Wang
Institute ofApplied Mathematics, Henan University, Kaifeng, 475004, P. R. China and
School ofMathematics and Statistics, Henan University, Kaifeng, 475004, P. R. China
Received 23 October 2013, accepted 9 October 2014, published online 11 June 2015
Abstract
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
378
Ars Math. Contemp. 8 (2015) 365-410
the plane such that every edge crosses at most one other edge. The concept of 1-planar graph was introduced by Ringel [9] in 1965, while he simultaneously colors the vertices and faces of a plane graph such that any pair of adjacent/incident elements receive different colors. Ringel [9] proved that every 1-planar graph is 7-colorable, and conjectured that every 1-planar graph is 6-colorable. In 1984, Borodin [1] confirmed this conjecture, and later Borodin [2] found a better proof for it. Recently, various coloring problems of 1-planar graphs are considered, see [4, 13, 10].
A connected graph H is strongly light in a family of graphs G, if there exists an integer A, such that every graph G in G contains a subgraph K isomorphic to H with degG(v) < A for all v € V(K). A graph H is said to be light in a family G of graphs if at least one member of G contains a copy of H and there is an integer A(H, G) such that each member G of G with a copy of H also has a copy K of H such that degG (v) < A(H, G) for all v € V(K). Note that a light subgraph may be not strongly light, for example, the graph K5 is light in the family of graphs G = {planar graphs} U {K6}, but K5 is not strongly light in G since not every graph in G contains a subgraph K5. The light subgraphs are well studied when G is a subclass of planar graphs, and we refer the reader to a good survey [8].
Fabrici and Madaras [5] studied the structure of 1-planar graphs, mainly on the light subgraphs of 1-planar graphs. They showed that every 3-connected 1-planar graph contains an edge with each end having degree at most 20, and this bound is the best possible. Hudik and Madaras [6] proved that each 1-planar graph of minimum degree 5 and girth 4 contains (i) a 5-vertex adjacent to a vertex of degree at most 6, (ii) a 4-cycle whose vertices all have degree at most 9 (the upper bound was further improved to 8 by Borodin, Dmitriev and Ivanova [3]), (iii) a star K14 with all vertices having degree at most 11.
In 1965, Ringel [9] found that each 1-planar graph has a vertex of degree at most 7 and the bound is tight. Hudik and Madaras [7] considered strongly light subgraphs in the family of 1-planar graphs with minimum degree 7, and proved the following theorem.
Theorem 1.1 (Hudik and Madaras [7]). Each 1-planar graph with minimum degree 7 contains
(a)	two adjacent 7-vertices,
(b)	a K4 whose vertices all have degree at most 13,
(c)	a K2*3 whose vertices all have degree at most 13, where K2 3 is a graph K2,3 with an extra edge between two vertices of the smaller bipartition,
(d)	a W4 whose vertices all have degree at most 11.
In this paper, we also consider strongly light subgraphs in the family of 1-planar graphs with minimum degree 7.
2 Strongly light subgraphs
Let G be a graph having been drawn in a surface; if we treat all the crossing points as vertices, then we obtain an embedded graph Gt, and call it the associated graph ofG, call the vertices of G true vertices and the crossing points crossing vertices. In the associated graph, a 3-face is called a false 3-face if it is incident with a crossing vertex; otherwise, it is a true 3-face. Clearly, a false 3-face is incident with exactly one crossing vertex. Note that the set of crossing vertices in the associated graph is independent. In the figures of this
T. Wang: Strongly light subgraphs in the 1-planar graphs with minimum degree 7	411
paper, the solid dots denote true vertices and the hollow dots denote crossing vertices, and some degree restrictions are beside the vertices.
Zhang et al. presented two strongly light subgraphs on four vertices in the family of 1-planar graphs with minimum degree 7.
Theorem 2.1 (Zhang et al. [14]). Each 1-planar graph with minimum degree 7 contains a K4 with all vertices of degree at most 11.
Theorem 2.2 (Zhang et al. [11]). Each 1-planar graph with minimum degree 7 contains a 4-cycle C = [x1 x2x3x4] with a chord x1 x3, where deg(x1) = 7, deg(x2) < 10, deg(x3) < 8 and deg(x4) < 10.
We improve the above two results to the following. A K4 is of type (d1, d2, d3, d4) if its degrees are d1, d2, d3 and d4, respectively. Similarly, we can define a K4 of type (dj+, d+, d+, d+), etc.
Theorem 2.3. If G is a 1-planar graph with minimum degree 7, then it contains a K4 of the type (7,8-, 8-, 10-).
Proof. Suppose that G is a connected counterexample to the theorem, which implies that G contains no K4 or every copy of K4 is of the type (8+, 8+, 8+, 8+) or (7,9+, 9+, 9+) or (7,8-, 9+, 9+) or (7,8-, 8-, 11+).
Furthermore, we may assume that G has been 1-embedded in the plane. Clearly, every face of its associated graph is homeomorphic to an open disk. Let Kt be the associated graph of G. By Euler's formula, we have
^ (degKt (v) - 6) + ^ (2 degKt (f - 6) = -12.	(2.1)
veV(Kt)	f eF(Kt)
We will use the discharging method to complete the proof. The initial charge of every vertex v is degKt (v) - 6, and the initial charge of every face f is 2degKt (f) - 6. By (2.1), the sum of all the elements' charge is -12. We then transfer some charge from the 4+-faces and the 7+-vertices to crossing vertices, such that the final charge of every crossing vertex becomes nonnegative and the final charge of every 4+-face and every 7+-vertex remains nonnegative, and thus the sum of the final charge of vertices and faces is nonnegative, which leads to a contradiction. The Discharging Rules:
(R1) every 4+-face donates its redundant charge equally to incident crossing vertices;
(R2) every 7+-vertex donates its redundant charge equally to incident false 3-faces;
(R3) after applying (R2), every false 3-face donates its redundant charge to the incident crossing vertex.
By the discharging rules, the final charge of every face and every 7+-vertex is nonnegative. So it suffices to consider the final charge of crossing vertices in Kt.
By the construction of Kt, every face is incident with at most [^gf(v) j crossing vertices. Thus, every 4+-face sends at least 1 to each incident crossing» vertex.
Note that every 7+-vertex v is incident with at most 2 (v) j false 3-faces. More formally, every 7-vertex sends at least 6 to each incident false 3-face; every 8-vertex sends
378
Ars Math. Contemp. 8 (2015) 365-412
(a)
at least 1 to each incident false 3-face; every 9-vertex sends at least | to each incident false 3-face; every 10-vertex sends at least 2 to each incident false 3-face; every ll+-vertex
5
sends at least 2 to each incident false 3-face.
Let w be an arbitrary crossing vertex in Kt. Notice that the four neighbors of w are 7+-vertices.
If w is incident with at least two 4+-faces, then its final charge is greater than 4 -6 + 2 x 1 = 0. If w is incident with exactly one 4+-face, then its final charge is at least 4 - 6 + 1 + 6 x 6 = 0.
If there is no crossing vertex which is incident with four 3-faces, then the sum of the final charge is nonnegative, which leads to a contradiction. So we may assume that w is incident with four 3-faces. It is obvious that the four neighbors of w induce a K4 in G. If this K4 is of the type (8+, 8+, 8+, 8+), then the final charge of w is at least 4 - 6 + 8 x 1 = 0; if this K4 is of the type (7,9+, 9+, 9+), then the final charge of w is at least 4 - 6 + 2 x 1 + 6 x 8 > 0; if this K4 is of the type (7,8-, 9+, 9+), then the final charge of w is at least 4 - 6 + 4 x 6 + 4 x 3 > 0; if this K4 is of the type (7,8-, 8-, 11+), then the final charge of w is at least 4 - 6 + 6 x 6 + 2 x 1 = 0.
Finally, all the faces and vertices have nonnegative charge, which leads to a contradiction.	□
To the author's knowledge, all the known strongly light graphs have at most five vertices. Now, we give a strongly light graph on 8 vertices in the family of 1-planar graphs with minimum degree 7.
Theorem 2.4. If G is a 1-planar graph with minimum degree 7, then G contains a subgraph as illustrated in Fig. (a). Moreover, (i) every vertex in {w2, w3,..., w7} has degree at most 23; (ii) at most one vertex in {w2, w3,..., w7} is a 12+-vertex; (iii) if no vertex in
{w2, w3, w5, w7} is a 7-vertex, then w2w3, w3w4, w4w5, w5w6, w6w7, w7w1 € E(G).
Proof. Suppose that G is a connected 1-planar graph with minimum degree 7, and it has been 1-embedded in the plane. Clearly, every face of its associated graph is homeomorphic to an open disk. Let Kt be the associated graph of G. By Euler's formula, we have
^ (degKt(v) - 4) + ^ (degKt(f) - 4) = -8.	(2.2)
v€V(Kt)	f€F(Kt)
We will use the discharging method to complete the proof. The initial charge of every vertex v is degKt (v) - 4, and the initial charge of every face f is degKt (f) - 4. By (2.2), the
T. Wang: Strongly light subgraphs in the 1-planar graphs with minimum degree 7	413
sum of all the elements' charge is -8. We then transfer some charge from the 7+-vertices to the 3-faces, such that the final charge of every face and every 8+-vertex is nonnegative, thus there exists a 7-vertex such that its final charge is negative and the local structure is desired.
The Discharging Rules:
(R1) every 7+-vertex sends 1 to each incident false 3-face and sends 3 to each incident true 3-face;
(R2) let f be a face with a face angle w1ww2 and deg(w) = k > 8,
(a)	if f is a 3-face with deg(w1) = 7 and deg(w2) > 8, then w sends - 1 to w1 through f;
(b)	if f is a 3-face with deg(w1) = deg(w2) = 7, then each of w1 and w2 receives kk4 - 6 from w through f;
(c)	if f is a false 3-face with crossing vertex w1 and w1 is on the edge uw of G, then w sends 1 - 1 to w2 through f, and additionally w sends 1 - 4 to u through
f;
(d)	if f is a 4+-face with crossing vertex w1 and w1 is on the edge uw of G, then w sends ^ to u through f.
By the discharging rules, the final charge of every face and every 8+-vertex is nonnegative. Hence, there exists a 7-vertex w0 such that its final charge is negative.
If w0 is incident with at least one 4+-face, then its final charge is at least 7 - 4 - 6 x 1 = 0. So we may assume that w0 is incident with seven 3-faces. Notice that the number of incident false 3-faces is even. If w0 is incident with at most four false 3-faces, then its final charge is at least 7 - 4 - 4 x I - 3 x 1 = 0. Hence, the vertex w0 must be incident with six false 3-faces and one true 3-face. We also notice that w0 receives less than 3 from all the other vertices; otherwise, its final charge is at least 7 - 4 + 3 - 6 x 1 - I = 0.
Let w1 w0w2 be the true 3-face. If both w1 and w2 are 8+-vertices, then w0 receives at least 1 - 3 = 6 from each of w1 and w2 by (R2-a), thus w0 receives at least 1 from all the other vertices, a contradiction. Hence, at least one of w1 and w2 must be a 7-vertex, so we may assume that w1 is a 7-vertex, see Fig. (a).
(i)	Suppose that w0 is adjacent to a 24+ -vertex w in G. By the discharging rules, the vertex w0 receives at least 2 x (12 - 4) = 1 from w, which leads to a contradiction. Hence, every vertex in {w2, w3,..., w7} has degree at most 23.
(ii)	If at least two vertices in {w2, w3,..., w7} are 12+-vertices, then w0 will receive at least 4 x (1 - 1) = 3, which leads to a contradiction. Hence, at most one vertex in {w2, w3,..., w7} is a 12+-vertex.
(iii)	Suppose, to derive a contradiction, that w2w3, w3w4, w4w5, w5w6, w6w7, w7w1 € E(G) does not hold. Thus, at least one crossing vertex in Fig. (a) is incident with a 4+-face. By (R2-d), the vertex w0 receives at least 1 from a 8+-vertex through a 4+-face. By (R2-b), the vertex w0 receives at least 4 - 1 = l) from w2 through the true 3-face w0w1w2, thus it receives at least 1 + 12 = 3 from all the other vertices, which derives a contradiction. □
Corollary 2.5 (Hudik and Madaras [7]). If G is a 1-planar graph with minimum degree 7, then it contains an edge such that each end has degree exactly 7.
378
Ars Math. Contemp. 8 (2015) 365-414
(b)	(c)	(d)	(e)	(f)
Corollary 2.6. Every 1-planar graph with minimum degree 7 contains a Ki,7 with the center of degree 7 and the other vertices of degree at most 23.
By Theorem 2.4, the wheel W4 is strongly light in the family of 1-planar graphs with minimum degree 7. In the next theorem, we further improve the degree restriction on each vertex in W4.
Theorem 2.7. If G is a 1-planar graph with minimum degree 7, then G contains at least one subgraph as illustrated in Fig. (b)-(f).
Proof. Suppose that G is a connected 1-planar graph with minimum degree 7, and it has been 1-embedded in the plane. Clearly, every face of its associated graph is homeomorphic to an open disk. Let Kt be the associated graph of G. By Euler's formula, we have
£ (degKt(v) - 4) + £ (degKt(f) - 4) = -8.	(2.3)
veV(Kt)	f €F(Kt)
We will use the discharging method to complete the proof. The initial charge of every vertex v is degKt (v) - 4, and the initial charge of every face f is degKt (f) - 4. By (2.3), the sum of all the elements' charge is -8. We then transfer some charge from the 7+-vertices to the 3-faces, such that the final charge of every face and every 8+-vertex is nonnegative, thus there exists a 7-vertex such that its final charge is negative and the local structure is desired.
The Discharging Rules:
(R1) every 7+-vertex sends 1 to each incident false 3-face and sends 3 to each incident true 3-face;
(R2) let f be a face with a face angle w1 ww2 and deg(w) = k > 8,
(a)	if f is a 3-face with deg(w1) = 7 and deg(w2) > 8, then w sends k-4 - 1 to w1 through f;
(b)	if f is a 3-face with deg(w1) = deg(w2) = 7, then each of w1 and w2 receives
k-4 1
2k 6
k-k4 - 6 from w through f;
(c) if f is a false 3-face with crossing vertex w1, then w sends ^ - 2 to w2 through
f. k 2
By the discharging rules, the final charge of every face and every 8+-vertex is nonnegative. Hence, there exists a 7-vertex w0 such that its final charge is negative.
If w0 is incident with at least one 4+ -face, then its final charge is at least 7 - 4 - 6 x 1 = 0. So we may assume that w0 is incident with seven 3-faces. Notice that the number of incident
T. Wang: Strongly light subgraphs in the 1-planar graphs with minimum degree 7	415
false 3-faces is even. If w0 is incident with at most four false 3-faces, then its final charge is at least 7 - 4 - 4 x 1 - 3 x 1 = 0. Hence, the vertex w0 must be incident with six false 3-faces and one true 3-face. We also notice that w0 receives less than 3 from all the other vertices; otherwise, its final charge is at least 7 - 4 + 3 - 6 x 1 - 1 = 0.
Let w1 w0w2 be the true 3-face. If both w1 and w2 are 8+-vertices, then w0 receives at least 1 - 3 = 6 from each of w1 and w2 by (R2-a), thus w0 receives at least 1 from all the other vertices, a contradiction. Hence, at least one of w1 and w2 must be a 7-vertex, so we may assume that w1 is a 7-vertex, see Fig. (a).
Case 1. Both deg(w4) and deg(w6) belong to {7,8}.
Since the vertex w0 receives less than 3 from the vertex w2, it follows that (^ggWW)-4 -1) + (dries - 1) < 1 and deg(w2) < 12, see Fig. (b). Case 2. Exactly one of deg(w4) and deg(w6) belongs to {7,8}.
Note that max{deg(w4), deg(w6)} > 9, if w2 is a 10+ -vertex, then w0 receives at least 2x (9 - |)+(f - 2)+(1s - 6) > 1, a contradiction. So we may assume that w2 is a9--vertex. If w2 is a 7-vertex and max{deg(w4), deg(w6)} > 12, then w0 will receive at least 2x(| -1) = 3, which is a contradiction. If w2 is a 8-vertex and max{deg(w4), deg(w6)} > 11, then w0 will receive at least 2 x (11 - 2) + (4 - 5) > 3, a contradiction. If w2 is a 9-vertex and max{deg(w4), deg(w6)} > 10, then w0 receives at least 2 x (| - 1) + (5 -1) + (18 - 6) = 11 > 3, which leads to a contradiction. In summary, if w2 is a 7-vertex, then max{deg(w4), deg(w6)} € {9,10,11}, and thus G contains a subgraph isomorphic to that in Fig. (b); if w2 is a 8-vertex, then max{deg(w4), deg(w6)} € {9,10}, and thus G contains a subgraph isomorphic to that in Fig. (b) or Fig. (c); if w2 is a 9-vertex, then max{deg(w4), deg(w6)} = 9, and thus G contains a subgraph isomorphic to that in Fig. (d), Fig. (e) or Fig. (f).
Case 3. Both deg(w4) and deg(w6) are at least 9.
If w2 is a 9+-vertex, then the vertex w0 will receive at least (H - 1) + 5 x (9 - 1) > 3, a contradiction. So we may assume that w2 is a 7- or 8-vertex. If min{deg(w4), deg(w6)} > 10, then the vertex w0 will receive at least 4 x (| - 1) = | > 1, a contradiction. Hence, we have that min{deg(w4), deg(w6)} = 9. If w2 is a 7-vertex and max{deg(w4), deg(w6)} > 11, then the vertex w0 will receive at least 2 x (11 - 2) + 2 x (9 - 2) > 3, a contradiction. If w2 is a 8-vertex and max{deg(w4), deg(w6)} > 10, then w0 will receive at least 2 x (5 - 2) + 2 x (9 - 2) + (4 - 1 ) > 3, which is a contradiction. In summary, if w2 is a 7-vertex, then G contains a subgraph as illustrated in Fig. (e); if w2 is a 8-vertex, then G contains a subgraph as illustrated in Fig. (f).	□
Corollary 2.8. If G is a 1-planar graph with minimum degree 7, then G contains a triangle having vertex degree 7, 7 and at most 9, respectively.
As an immediate consequence of Theorem 2.7, the following corollary is an improvement of Theorem 2.2.
Corollary 2.9. If G is a 1-planar graph with minimum degree 7, then G contains a 4-cycle
C = [x1 x2x3x4] with a chord x1 x3, where deg(x1) = 7, deg(x2) < 9, deg(x3) < 8 and deg(x4) < 9.
378
Ars Math. Contemp. 8 (2015) 365-416
Corollary 2.10 ([12]). If G is a 1-planar graph with minimum degree 7, then G contains a copy of K1 v (K1 u K2) with all the vertices of degree at most 9.
Acknowledgments. The author was supported by NSFC (11101125) and partially supported by the Fundamental Research Funds for Universities in Henan. The author would like to thank the anonymous reviewers for their valuable comments and assistance on earlier drafts.
References
[1]	O. V. Borodin, Solution of the Ringel problem on vertex-face coloring of planar graphs and coloring of 1-planar graphs, Metody Diskret. Analiz. 41 (1984), 12-26, 108.
[2]	O. V. Borodin, A new proof of the 6 color theorem, J. Graph Theory 19(4) (1995), 507-521.
[3]	O. V. Borodin, I. G. Dmitriev and A. O. Ivanova, The height of a cycle of length 4 in 1-planar graphs with minimal degree 5 without triangles, Diskretn. Anal. Issled. Oper. 15(1) (2008), 11-16.
[4]	O. V. Borodin, A. V. Kostochka, A. Raspaud and E. Sopena, Acyclic colouring of 1-planar graphs, Discrete Appl. Math. 114(1-3) (2001), 29-41.
[5]	I. Fabrici and T. Madaras, The structure of 1-planar graphs, Discrete Math. 307(7-8) (2007), 854-865.
[6]	D. Hudik and T. Madaras, On local structure of 1-planar graphs of minimum degree 5 and girth 4, Discuss. Math. Graph Theory 29(2) (2009), 385-400.
[7]	D. Hudik and T. Madaras, On local properties of 1-planar graphs with high minimum degree, Ars Math. Contemp. 4(2) (2011), 245-254.
[8]	S. Jendrol and H.-J. Voss, Light subgraphs of graphs embedded in the plane—a survey, Discrete Math. 313(4) (2013), 406-421.
[9]	G. Ringel, Ein Sechsfarbenproblem auf der Kugel, Abh. Math. Sem. Univ. Hamburg 29(1) (1965), 107-117.
[10]	X. Zhang and G. Liu, On edge colorings of 1-planar graphs without adjacent triangles, Inform. Process. Lett. 112(4) (2012), 138-142.
[11]	X. Zhang andG. Liu, On the lightness of chordal 4-cycle in 1-planar graphs with high minimum degree, Ars Math. Contemp. 7 (2014), 281-291.
[12]	X. Zhang, G. Z. Liu and J. L. Wu, Light subgraphs in the family of 1-planar graphs with high minimum degree, Acta Math. Sin. (Engl. Ser.) 28(6) (2012), 1155-1168.
[13]	X. Zhang and J.-L. Wu, On edge colorings of 1-planar graphs, Inform. Process. Lett. 111(3) (2011), 124-128.
[14]	X. Zhang, J.-L. Wu and G. Liu, New upper bounds for the heights of some light subgraphs in 1-planar graphs with high minimum degree, Discrete Math. Theor. Comput. Sci. 13(3) (2011), 9-16.