/^creative ^commor
ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 7 (2014) 281-291
On the lightness of chordal 4-cycle in 1-planar graphs with high minimum degree*
Xin Zhang t
Department of Mathematics, Xidian University, Xi'an 710071, P. R. China
Guizhen Liu *
School of Mathematics, Shandong Univeristy, Jinan 250100, P. R. China Received 12 January 2012, accepted 8 February 2013, published online 7 May 2013
Abstract
A graph G is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. The family of 1-planar graphs with minimum vertex degree at least S and minimum edge degree at least e is denoted by V¿ (e). In this paper, it is proved that every graph in V7 (14) (resp. Vg (13)) contains a copy of chordal 4-cycle with all vertices of degree at most 10 (resp. 12).
Keywords: 1-planar graph, light graph, cycle, discharging. Math. Subj. Class.: 05C75, 05C10
1 Introduction
All graphs considered in this paper are finite, undirected, loopless and without multiple edges. For a graph G, we use V(G), E(G), 5(G) and A(G) to denote the vertex set, the edge set, the minimum degree and the maximum degree of G, respectively. By F(G), we denote the face set of G when G is a plane graph. If uv g E(G), then u is said to be the neighbor of v. We use NG(v) to denote the set of neighbors of a vertex v. The degree of a vertex v g V(G), denoted by dG(v), is the value of |NG(v)|, and the degree of an edge uv g E(G), denoted by dG(uv), is the value of dG(u) + dG(v). A k-, k+-and k--vertex is a vertex of degree k, at least k and at most k, respectively. In this paper, Ck and Pk denotes a cycle and a path with k vertices and K- denotes a chordal 4-cycle, which is a
*	A project funded by Scientific Research Program of the Higher Education Institution of Xinjiang (Grant No. XJEDU2012I38) and the Fundamental Research Funds for the Central Universities (Grant No. K5051370003).
t Supported in part by the National Natural Science Foundation of China (Grants No. 11101243, 11201440).
*	Supported in part by the National Natural Science Foundation of China (Grants No. 61070230).
E-mail addresses: xzhang@xidian.edu.cn (Xin Zhang), gzliu@sdu.edu.cn (Guizhen Liu)
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
340
284	Ars Math. Contemp. 7 (2014) 281-63
graph obtained by removing an edge from a complete graph K4. A cycle C = [x • • • xk] of a graph G is of the type (d\, • • • ,dk) if dc(xj) = dj for 1 < i < k. Similarly we can define cycles of the type (> d1, • • • , > dk), etc. For other undefined concepts we refer the readers to [2].
A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. The notion of 1-planarity was introduced by Ringel [16] while trying to simultaneously color the vertices and faces of a plane graph G such that any pair of adjacent/incident elements receive different colors. Note that we can construct, for given plane graph, a 1-planar graph G1 whose vertex set is V(G) U F(G) and any two vertices of G1 are adjacent if and only if their corresponding elements in G are adjacent or incident.
Borodin proved that each 1-planar graph is 6-colorable (the bound 6 being sharp) [3,4] which positively answered a conjecture raised by Ringel in [16], and that each 1-planar graph is acyclically 20-colorable [7]. The list analogue of vertex coloring of 1-planar graphs was investigated by Albertson and Mohar [1], and by Wang and Lih [18]. Zhang et al. showed that each 1-planar graph G with maximum degree A is A-edge-colorable if A > 10 [25], or A > 9 and G contains no chordal 5-cycles [19], or A > 8 and G contains no chordal 4-cycles [20], or A > 7 and G contains no 3-cycles [21], is (A + 1)-edge-choosable and (A + 2)-total-choosable if A > 16 [27], is A-edge-choosable and (A + 1)-total-choosable if A > 21 [27]. Zhang et al.also showed that the (p, 1)-total labelling number of each 1-planar graph G is at most A(G) + 2p - 2 if A(G) > 8p + 4 [28], and the linear arboricity of each 1-planar graph G is exactly [A(G)/2] if A(G) > 33 [24].
Another topic concerning 1-planar graphs is to investigate their global and local structures. In [9], it is shown that each 1-planar graph with n vertices has at most 4n - 8 edges and this upper bound is tight, which implies that the minimum vertex degree of any 1-planar graph is at most 7.
Let H be a connected graph and G be a family of graphs. If for any graph G G G, G contains a subgraph K ~ H such that
max {dG(x)} < th < and > dG(x) < tw <	(1.1)
xev (K)	^
y '	xev(K)
then we say that H is light in G, and otherwise say that H is heavy in G. The smallest integers th and tw satisfying (1.1) are called the height and the weight of H in the family G, denoted by h(H, G) and w(H, G), respectively. By L(G), we denote the set of light graphs in the family G. Throughout this paper, Vi (e) (resp. V (e)) denotes the family of 1-planar graphs (resp. planar graphs) with minimum vertex degree at least S and minimum edge degree at least e. If e = 2S, we use the natation Vi (resp. V) for short to represent Pi (e) (resp. V (e)). Note that for the parameter Vj(e), we need to assume that S < 7 and e > 2S.
The first complete description of the set of light graphs in the family of 1-planar graphs with high minimum degree was given in [9, 22]; there was proved that L(V|) = {Pi,P2,P3}. Fabrici and Madaras [9], Zhang, Liu and Wu [22], and Dong [8] together proved that ^(Vg1) = {P1, P2, P3, P4, S3}, where S3 is a 3-star. For the lightness of some graphs in the family Vj where 6 < S < 7, the readers can refer to [6, 9, 11, 10, 12, 13, 17, 22, 26, 23].
In this paper, we investigate the lightness of some graphs in Vj (e) with not only e = 2S but also e > 2S, the later case of which has not been considered for the family of 1-planar graphs even before. Our motivation comes from the analogical results for planar graphs
X. Zhang and G. Liu: On the lightness ofchordal 4-cycle in 1-planar graphs with.
283
with minimum degree 5 and minimum edge degree 25 +1 where 5 G {3,4}. For example, Borodin proved in [5] that L(P3(7)) = {P1,P2, P3} (also proved in [14] by Madaras and Skrekovski), and Mohar et al. [15] presented some light subgraphs in the class P4(9).
In what follows, we show in Section 2.3 that K- is light in the family P7X as well as in its superfamily P^ (13), and its height is at most 10 and at most 12, respectively.
2 The lightness of chordal 4-cycle
2.1	Basic terms
In the following, we always assume that G is a 1-planar graph that has been drawn on a plane so that every edge is crossed by at most one another edge and the number of crossings is as small as possible. The associated plane graph Gx of G is the plane graph that is obtained from G by turning all crossings of G into new 4-vertices. A vertex in Gx is false if it is not a vertex of G; otherwise, it is true. Similarly, by false (resp. true) face, we mean a face in Gx that is incident with at least one false (resp. no false) vertices. Let v and f be a vertex and a face in Gx. The function Z(v) (resp. Z( f)) denotes the number of false vertices that are adjacent to v (resp. incident with f) in Gx.
For convenience, we introduce some specialized notations. Let v be a false vertex in Gx and let v1,v2,v3, v4 be its neighbors in a clockwise order. Define fi to be the face incident with vvf and vvi+1, where subscripts are taken modulo 4. Note that if d(fi) = 3, then vivi+1 g E(G). In this case, let f' be the other face incident with the edge vivi+1. If d(f') = 3, then its third vertex will be denoted by v'i. Thus v'i is a false vertex if and only if fi is false, in which case we denote a neighbor of vi (resp. vi+1) in G to be vi' (resp. vi'+1), so that vivi'i and vi+1 vi'+1 are two edges in G that crossed by each other at the point vi. Denote the face that is incident with the path vivi'vi'+1 (resp. vi+1vivi') in Gx by fL (resp. fR).
While proving the lightness of a graph in a given family of graphs, usually, the discharging method is used. In the proof of this paper, based on this method we consider a hypothetical counterexample G (a 1-planar graph) and then construct its associated plane graph Gx. We first assign an initial charge c to each element x G V(Gx)UF(Gx) as follows:
c(x)=j adQ" (x) - 2(a + pl if x G V(Gx);
C(X) 1 PdGx (x) - 2(a + p), if x G F(Gx),	( )
where a and P are some prescribed positive numbers. By combining the Euler formula
|V(Gx)| - |E(Gx)| + |F(Gx)| =2 on Gx and the relation £vEV(GX) dGx (v) =
E f eF (GX) dGx (f) = 2|E(Gx ) |, wehave ExeV (GX) J F (gx) c(x) = -4(a + P) <
We then redistribute the charge of the vertices and the faces of Gx according to some discharging rules, which only move charge around but do not affect the total charges so that, after discharging, the final charge c' of each element in V(Gx) U F(Gx) is nonnegative. This leads to a contradiction that £xeV(Gx)y F(Gx) c(x) = ExEV(Gx^ F(Gx) c'(x) > 0 and completes the proof.
2.2	A key discharging lemma
Let G be a 1-planar graph and let v be a true vertex in its associated plane graph Gx. Denote F(v) to be the subgraph induced by the faces that are incident with v. Note that F(v) can be decomposed into many parts, each of which is one of the five clusters in Figure
284
Ars Math. Contemp. 7 (2014) 281-291
1-Cluster	2-Cluster (i>0)	3-Cluster
4-Cluster (i>0)	5-Cluster (i>0)
Figure 1: F (v) can be decomposed into the combination of the above five clusters
1, and any two parts of which are adjacent only if they have a common edge vw such that w is a true vertex. The hollow vertices in Figure 1 are false and the solid ones are true, and all the faces marked by f are 4+-faces.
Lemma 2.1. Let v be a 6+-vertex in the associated plane graph Gx of a 1-planar graph G. Assign v an initial charge c(v) = adGx (v) — 2(a + p), where a and p are some prescribed positive numbers satisfying 2a > p. Suppose that v sends out charges only by the following three discharging rules:
Rule A v transfers a charge of to each incident 3-face in Gx ;
Rule B If v is incident with two adjacent 3-faces f = [xvz] and f2 = [yvz] so that z is a false vertex in Gx, then v sends the charge X to z;
Rule C If v is incident with a 3-face f = [xvz] sharing a common edge vz with a 4+-face f2 so that z is a false vertex in Gx, then v sends the charge /i to z.
Denote c' (v) to be the final charge of v after applying the above rules. If dGx (v) is even with
X < i 2 — ^^ 1 (a + p),
3 dGx (v)
1 =4 X,
(2.2) (2.3)
or dGx (v) > 9 is odd with
or dGx (v) = 7 with
X < (2dr (v) — 12	a + ph
< V 3dGx (v) — 3	' h
1=2X,
X = / =
a + p 12
(2.4)
(2.5)
(2.6)
then c' (v) > 0.
X. Zhang and G. Liu: On the lightness ofchordal 4-cycle in 1-planar graphs with...
285
Proof. Denote « to be the number of ¿-clusters contained in F(v) and m; to be the charges sent out from v through an ¿-cluster. By their definitions, one can easily observe that
2ni + 2«2 + «3 + 3«4 + «5 < dGx (v).
(2.7)
For the case when dGx (v) is even, by (2.7) and the choices of A, ^ as in (2.2) and (2.3), we have
2a ft 5 c'(v) = C(v)--3-dGx (v) —
i=1
a + ft 3
dGx (v) — 2(a + ft) — Ani — ^«2 — 2^«4
>	a + ftdGx (v) — 2(a + ft) — A(2«i + 2«2 + «3 + 3« + «5)
>	^^dGx (v) — 2(a + ft) — AdGx (v)
a + ft , , N , ^ A1 2
> dGx (v) — 2(a + ft) H1 — = 0.
(a + ft)dGx (v)
Now, we consider the case when dGx (v) is odd. Here, note that
«2 + «3 + «4 + «5 > 1
(2.8)
since any copy of a 1-cluster consists even number of faces incident with v. By (2.7), (2.8) and the choices of A, ^ as in (2.4) and (2.5), we have
c'(v) = c(v) — 2a3 ft dGx (v) — ^ «im;
i
a + ft 3
a + ft
dGx (v) — 2(a + ft) — A«i — ^«2 — 2^«4 A
3 dGx (v) — 2(a + ft) — ^(2«i + 2«2 + «3 + 3«4 + «5) + A3	2
2 («2 + «3 + «4 + «5)
a + ft , , , ,	A , , . A
>	^^dGx (v) — 2(a + ft) — AdGx (v) + A
>	^dGx (v) — 2(a + ft) —	((vv))^63) (a + ft)(dGx (v) — 1) = 0.
For the particular case when dGx (v) = 7, we can deduce from (2.7) that
«i + «2 + 2«4 =
2«i + 2«2 + 3«4 2
+
1
«4
<
+
= 4. (2.9)
284
Ars Math. Contemp. 7 (2014) 281-67
Thus by (2.9) along with the choices of A and ^ as in the equation (2.6), we have
2a — ¡3	5
c'(v) = c(v)--3-dGx (v)	ni'mi
a + 3 3
a + 3 3
i=1
—	Ani — ^n-2 —
—	A(ni + n2 + 2n4)
> 0±l — 4A " 3
= 0.
Consequently, we complete the proof of this lemma.	□
2.3 The height of chordal 4-cycle in p (13) and P*
Theorem 2.2. Each 1-planar graph with minimum degree at least 6 contains at least one of the following configurations:
(a)	a pair of adjacent vertices of degree 6;
(b)	a 4-cycle C = [x1x2x3x4] of the type (6, < 12, < 8, < 12) with a chord x1x3;
(c)	a 4-cycle C = [x1x2x3x4] of the type (7, < 10, < 8, < 10) with a chord x1x3.
Proof. The proof of the theorem is carried out by the discharging method as described in Section 2.1. Suppose G is a counterexample to the theorem. Consider the associated plane graph Gx of G. Assign the charges to each element x e V(Gx) U F(Gx) as mentioned in the inequation (2.1) of Section 2.1 by choosing a = 2 and 3 = 3. If v is a true vertex in G, then dGx (v) = dG(v), so in the following we use d(v) for short to represent both of the two notions. A big vertex, semi-big vertex, intermediate vertex and semi-intermediate vertex refer to a vertex v e V(Gx) with d(v) > 13, d(v) > 11, 6 < d(v) < 12 and 6 < d(v) < 10, respectively. Therefore, a true vertex in Gx is either big or intermediate, and an intermediate vertex in Gx is either semi-big or semi-intermediate. By big face, we denote a face f e F(Gx) with degree at least 4. Now, we define the discharging rules as follows.
Rule 1 Each 6+-vertex sends 1 to each incident face; Rule 2 Each 4-vertex sends 1 to each incident false 3-face; Rule 3 Each big face sends 11 to each incident 4-vertex;
Rule 4 Let f be a big face having a common edge xy with a false 3-face g = [xyz] .If z is a 4-vertex, then f sends -5 to z through xy;
Rule 5 Let f be a big face having a common edge xy with a false 3-face g = [xyz]. If x ic q A.wm-w orH ic	with another false 3-face h = [yzu], then f sends 24
to u through xy and yz; Rule 6 Let f = [xyz] be a true 3-face having a common edge yz with a false 3-face
_5_
12
g = [uyz]. If d(x) > 11, then x sends to u through yz;
X. Zhang and G. Liu: On the lightness ofchordal 4-cycle in 1-planar graphs with.
68
Rule 7 Let f = [xyz] and g = [uyz] be two adjacent false 3-faces, and let z be a 4-vertex. Suppose yu is incident with another false 3-face h = [yuw] so that yy' crosses uu' in G at w. If at least one of the following four occasions appears in Gx
•	d(x) > 13, min{d(u), d(y)} = 6, max{d(u), d(y)} < 8 and y,u, u' are all intermediate vertices with yu' G E(Gx);
•	d(x) > 13, min{d(u), d(y)} = 6, max{d(u), d(y)} < 8 and y, u, y' are all intermediate vertices with uy' G E(Gx);
•	d(x) > 11, min{d(u), d(y)} = 7, max{d(u), d(y)} < 8 and y,u, u' are all semi-intermediate vertices with yu' G E(Gx);
•	d(x) > 11, min{d(u), d(y)} = 7, max{d(u), d(y)} < 8 and y,u,y' are all semi-intermediate vertices with uy' G E(Gx),
then x sends 2§4 to w through yz and yu;
Rule 8 Let f = [xyz] and g = [uyz] be two adjacent false 3-faces. If z is a 4-vertex, then y sends to z a charge of
12, if d(y) = 7;
|, if d(y) = 8; 4, if 9 < d(y) < 12; §, if d(y) > 13;
Rule 9 Let f = [xyz] be a false 3-face having a common edge yz with a big face If z is a 4-vertex, then y sends to z a charge of
12, if d(y) = 7; 8, if 8 < d(y) < 12; 8, if d(y) > 13.
In the following, we estimate the final charge c' of vertices and faces after the charge redistribution and prove c'(x) > 0 for each x G V(Gx ) U F(Gx). By Rules 1 and 2, any 3-face f in Gx receive 3 from each of its incident vertices, which implies the final charge of f is exactly zero. For a big face f in Gx (recall that Z(f) denotes the number of 4-vertices incident with f), it would send 11Z(f) to its incident 4-vertices by Rule 3. Besides, if f is incident with a 4-vertex v, then f send out 2 x 2§4 = 12 through uv and vw by Rule 5, where u and w denote the neighbors of v on the boundary of f. Since f is incident with d(f) - 2Z(f) true edges (namely, an edge of Gx containing no 4-vertex), by Rule 4, a total charge of 12 (d(f) —2Z(f)) would be sent out from f through the true edges incident with f. On the other hand, f receive 3 from each of d(f) —Z(f) true vertices incident with it. Since
Z(f) < ^, c'(f) > 3d(f) —10 —12Z(f) —12Z(f) —12(d(f)—2Z(f))+3(d(f)—Z(f)) = 3§d(f) — 6Z(f) — 10 > 2d(f) — 10 > 0 for d(f) > 4.
By Lemma 2.1 along with Rules 1,8 and 9, one can check that c'(v) > 0 for all vertices of degree between 6 and 10. For a big vertex v in Gx, denote F(v) to be the subgraph induced by the faces that are incident with v. As we state at the beginning of Section 2.2, F(v) can be decomposed into a combination of the five clusters in Figure 1. By and mj, we denote the number of ¿-clusters contained in F(v) and the charges sent out from v through an ¿-cluster. If there is a 2-cluster in F(v), then v send | to y (see Figure 1) by Rule 9 and at most 24 through xy by Rule 7, so m2 < | + 24 = |§. Similarly, we can prove
284
Ars Math. Contemp. 7 (2014) 281-69
that m3 < 12 by Rule 6, m4 < 2 x § + 2 x 24 = f§ by Rules 7, 9 and m5 = 0. We now estimate the value of mi much more carefully. First, we show the following observation.
Observation. If v is incident with a 1-cluster as in Figure 1 and has sent out some charge through xy by Rule 7, then it would not send out any charge through the edge yz.
Proof. Denote u to be the neighbor of v in G such that uv crosses xz in G at the point y. Suppose, on the contrary, that v send out some charge through yz. By the definitions of the rules, uyz is a 3-face in Gx and z is an intermediate vertex in Gx. Since v has sent out charge through xy by Rule 7, by the definition of Rule 7, we have xu G E(Gx), min{d(x), d(u)} = 6 and max{d(x), d(u)} < 8. Furthermore, xu is also incident with a 3-cycle, say xuw, in G such that w is an intermediate vertex in Gx different from z. Now, the four distinct vertices x, z, u, w form a 4-cycle [uwxz] in G with a chord ux, and therefore, the configuration (b) occurs in G. This contradiction verifies this observation. ||
By Rules 7, 8 and the above observation, we immediately have mi < § + 24 = i§. Therefore, by Rule 1 and the inequality (2.7) in Section 2.1, we have c'(v) > 2d(v) -10 - 1 d(v) - 1§ni - 24« - 12«3 - f|«4 > §d(v) - 10 - if (2ni + 2« + «3 + 3« + «5) + 2§(«2 + n3 + «4 +2 «5) > Hd(v) - 10 + 4§(«2 + n3 + «4 + «5) > 0 for d(v) > 14. If d(v) = 13, then by the inequality (2.8) in Section 2.1, we also have c'(v) > 4§d(v) - 10 + H =0 in final. For vertices of degree 11 or 12 (they are semi-big but not big), we can also check the nonnegativity of their final charges. Proof of them are left to the readers, since they use the same argument as in the previous analysis on the big vertices.
Now, the only missed case is when v is a 4-vertex in Gx (namely, v is a false vertex). As we know, the initial charge of a 4-vertex v is -2, so if v is incident with at least three big faces, then by Rules 2 and 3, the final charge c'(v) of v is at least -2 -1 + 3x 12 = H > 0. In the following, we discuss three other cases. Case 1. v is incident with exactly two 3-faces.
First, suppose that f1 and /2 are 3-faces. Since no two 6-vertices are adjacent in G, at least two of v1, v2 and v3 are 7+-vertices. Thus by Rules 8 and 9, each of the two 7+-vertices among v1, v2 and v3 would send at least h to v. Therefore, c'(v) > -2 - 2 x 1 + 2 x 11 + 2 x H = 0 by Rules 2, 3, 8 and 9.
Second, suppose that f1 and /3 are 3-faces. In this case, one can also show that there are at least two 7+-vertices among v1, v2, v3 and v4. Thus by Rules 2, 3, 8 and 9, we still have c'(v) > -2 - 2 x 3 + 2 x 11 + 2 x ^ =0.
Case 2. v is incident with exactly three 3-faces.
Without loss of generality, we assume that f1, /2, /3 are 3-faces and /4 is a 4+-face (recall the definitions of / in Section 2.1). By Rule 3, /4 shall send 11 to v.
First, suppose that at least two of v1, v2, v3 and v4, say v1 and v4 (other cases can be dealt with similarly), are big vertices. Thus at least one of v2 and v3 must be 7+-vertex since
they are adjacent in G. Therefore, by Rules 2, 3 and9, c'(v) > -2-3x 1 +2x §+H +11 =
0.	3 f 12 12
Next, suppose that only one of v1, v2, v3 and v4 is big vertex. If v2 or v3, say v2, is big, then at least one of v1, v3 and v4 should be a 7+-vertex since they three form a 3-path in G. By Rules 2, 3, 8 and 9, c'(v) > -2 - 3 x 1 + | + H + 11 =0. If v1 or v4, say v1, is big, then all of v2, v3 and v4 are intermediate. If they are all 7+-vertices, then c'(v) > -2 - 3 x 1 + § + 3 x H + 12 = 0 by Rules 2, 8 and 9. Thus we assume that at
X. Zhang and G. Liu: On the lightness ofchordal 4-cycle in 1-planar graphs with.
70
least one of v2, v3 and v4 is a 6-vertex. Here, we only consider the case when d(v3) = 6 and leave the discussions on the rest two cases to the readers, since they are quite similar. First, suppose d(v2) > 9. By Rules 3 and 8, v2,v2 and /4 shall send |, | and 22 to v, respectively, thus, c'(v) > —2 - 3 x l + | + | + 22 =0. Second, suppose d(v2) < 8. We now consider the face /2 (recall its definition in Section 2.1). If /2 is a big face in Gx, then by Rule 4, /2 sends 12 to v through the edge v2v3. If /2 is a true 3-face, then v2 (recall the corresponding definition in Section 2.1) must be a big vertex, because otherwise the configuration (b) would appear in G, meanwhile, v receives 12 from v2 through the edge
fL „„A fR
v2v3 by Rule 6. If /2 is false 3-face, then we consider the faces /2 and /2R (recall their
24
definitions in Section 2.1). If /L is a big face, then by Rule 5, /L sends 24 to v through the
edge v2v3. If /2L is a 3-face, then it must be false since it is incident with a false vertex v2. Since v2, v3, v4 and v3' (recall the definitions of v'' in Section 2.1) form a chordal 4-cycle with a chord v2 v3 in G, v3' must be a big vertex, and then v shall receive 22 from v3' through the edge v2v3 by Rule 7. Similarly, v would receive another 22 through the edge v2 v3 from either the face /2R or the vertex v2'. Hence, through the edge v2v3, v shall totally receive a charge of 2 x 24 = 22. Since neither v2 nor v4 can be a 6-vertex (because each of them is adjacent to the 6-vertex v3 in G), each of v2 and v4 shall send 12 to v by Rules 8 and 9. Thus, by Rules 2, 3 and 9, we still have c'(v) >—2 — 3 x 1 + 22 + 2 x 22 + 6 + 11 =0.
At last, suppose none of v2, v2, v3 and v4 is big. If v2 or v3, say v2, is a 6-vertex, then v2, v3 and v4 are 7+-vertices since each of them is adjacent to v2. Furthermore, d(v3) > 9, because otherwise the configuration (b) would appear in G, so by Rules 2, 3, 8 and 9, we havec'(v) > —2 — 3x 1 + 2x 22 +1 +12 = 0. Wenowassumemin{d(v2), d(v3)} > 7. If max{d(v2), d(v3)} > 9 (without loss of generality, assume d(v3) > 9), then by Rules 2, 3, 8 and9, c'(v) > —2 —3x 2 +2x | + 22 > 0 whend(v2) > 9, c'(v) > —2 —3x 2 + 2x 22 + | + 22 =0 whend(v2) < 8andd(v1) > 7,andc'(v) > —2 — 3x 3 +12 +12 + +11 = 0 when d(v2) < 8 and d(v2) = 6 (note that in this case, a charge of at least H shall be transferred to v through the edge v2v2). Therefore, we assume max{d(v2), d(v3)} < 8 in the following. First, suppose at least one of v2 and v3 is a 8-vertex. Without loss of generality, suppose d(v2) = 7 and d(v3) = 8. By Rule 8, v2 and v3 shall send 12 and 6 to v, respectively. By a similar argument as above, v shall also receive 12 either from the vertex v2 when d(v2) > 7 or through the edge v2v2 when d(v(2) = 6, and another 12 either from the vertex v4 when d(v4) > 7 or through the edge v3v4 when d(v(4) = 6. Thus, by Rules 2 and 3, we have c'(v) >—2 — 3 x 3 + 12 + 6 + 2 x 12 + 22 =0.
Second, suppose d(v2) = d(v3) = 7. Under this hypothesis, at least one of v2 and v4 should be semi-big, because otherwise a configuration (c) would appear in G. If v1 and v4 are 8+-vertices, then by Rules 2, 3, 8 and9, c'(v) > —2 —3x 2 + 2 x 22 + 2x § + 22 = 0. If one of v2 and v4, say v4, is a 7--vertex, then by a similar argument as before, we can show that v receives 12 through the edges v2 v2 and another 12 through the edges v2 v3. Therefore, by Rules 2, 3, 8 and 9, we have c'(v) >—2 — 3 x 2 + 2 x 12 + § + 2 x 12 + 22 > 0.
Case 3. v is incident with four 3-faces.
If at least two of v2, v2, v3 and v4 are big vertices, then by Rules 2 and 8, c'(v) > —2 — 4 x 3 + 2 x | =0.
If only one of v2, v2, v3, v4, say v2, is a big vertex, then we can assume that v2, v3 and v4 are 7+ -vertices. Otherwise, without loss of generality, suppose d(v2) = 6. Since no two 6-vertices are adjacent in G, d(v3) > 7 and d(v4) > 7. If v3 and v4 are 8+-vertices, then c'(v) >—2 — 4 x 3 + | + 2 x | = 0 by Rules 2 and 8. We now assume that one of v3 and v4, say v3, is a 7-vertex. If now d(v4) > 9, then c'(v) >—2 — 4 x 2 + 3 + 112 + | = 0
284
Ars Math. Contemp. 7 (2014) 281-71
Rules 2 and 8. If d(v4) < 8, then by a similar argument as in Case 1, we can show that v receives 12 through the edges v2v3 and another 12 through the edges v3v4. Therefore, by Rules 2 and 8, c'(v) > -2 - 4 x 1 + § + 2 x 12 + 2 x 12 =0. Hence, we can assume min{d(v2), d(v3), d(v4)} > 7. If at least one of v2, v§ and v4 is a 8+-vertex, then by Rules 2 and 8, c'(v) > -2 - 4 x § + 2 x 12 + § =0. If d(v2) = d(v§) = d(v4) = 7, then by a similar argument as in Case 1, one can show that a charge of 12 would be transferred to v through each of the edges v2v3 and v3v4. Hence, by Rules 2 and 8, we have c'(v) > -2 - 4 x 1 +3 x 12 + 2 x 12 > 0.
We now consider the last case when vi, v2, v3 and v4 are intermediate vertices. If they all are 8+-vertices, then by Rules 2 and 8, c'(v) > -2 - 4 x 1 +4 x | = 0. If one of them, say v1, is a 6-vertex, then v2, v3 and v4 are 9+-vertex, because otherwise the configuration (b) would appear in G. This implies that c'(v) > -2 - 4 x 1 +3 x § > 0 by Rules 2 and 8. We now assume that d(v1) = 7 and min{d(v2), d(v3), d(v4)} > 7. If at least two of v2, v3 and v4 are 9+-vertices, then by Rules 2 and 8, c'(v) > -2 - 4 x 1 +2 x 12 + 2 x § = 0. Thus, we assume that at least two of v2, v3, v4, say v2 and v3, are 8--vertices. In this case, v4 should be a semi-big vertex because otherwise the configuration (c) would occur in G. If d(v2) = d(v3) = 8, then by Rules 2 and 8, c'(v) > -2 - 4 x 1 + 152 + 2 x § + § =0. If min{d(v2), d(v3)} = 7, then by a similar argument as in Case 1, one can prove that a charge of 12 would be transferred to v through each of the edges v1v2 and v2 v3. This implies that c'(v) > -2 - 4 x 3 + 3 x 1§2 + 2 x 1§2 + § =0.
Hence, we deduce that J2xev(g*^ f(g* ) c'(x) > 0. This contradiction completes the proof.	□
Corollary 2.3. K- e £(^1(13)) and h(K-, P1(13)) < 12.
Corollary 2.4. K4- e £(P1) and h(K4-, Pi) < 10.
Corollary 2.5. h(P2,P61) < 8 and w(P2,P61) < 15.
References
[1]	M. O. Albertson and B. Mohar, Coloring vertices and faces of locally planar graphs. Graph. Combinator. 22 (2006), 289-295.
[2]	J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, North-Holland, New York, 1976.
[3]	O. V. Borodin, Solution of Ringel's problems on the vertex-face coloring of plane graphs and on the coloring of 1-planar graphs (in Russian), Diskret. Analiz 41 (1984), 12-26.
[4]	O. V. Borodin, A New Proof of the six Color Theorem, J. Graph Theory 19 (1995), 507-521.
[5]	O.V. Borodin, Minimal vertex degree sum of a 3-path in plane maps, Discuss. Math. Graph Theory 17 (1997), 279-284.
[6]	O. V. Borodin, I. G. Dmitriev and A. O. Ivanova, The height of a 4-cycle in triangle-free 1-planar graphs with minimum degree 5, J. Appl. Industrial Math. 3 (2009), 28-31.
[7]	O. V. Borodin, A. V. Kostochka, A. Raspaud and E. Sopena, Acyclic colouring of 1-planar graphs, Discrete Appl. Mat. 114 (2001), 29-41.
[8]	W. Dong, Light paths of 1-planar graphs with bounded minimum degree, manuscript.
[9]	I. Fabrici and T. Madaras, The structure of 1-planar graphs, Discrete Math. 307 (2007), 854865.
X. Zhang and G. Liu: On the lightness ofchordal 4-cycle in 1-planar graphs with.
72
[10]	D. Hudak and T. Madaras, On local structures of 1-planar graphs of minimum degree 5 and girth 4, Discuss. Math. Graph Theory 29 (2009), 385-400.
[11]	D. Hudak and T. Madaras, On local properties of 1-planar graphs with high minimum degree, Ars Math. Contemp. 4 (2011), 245-254.
[12]	V. P. Korzhik, Minimal non-1-planar graphs, Discrete Math. 308 (2008), 1319-1327.
[13]	V. P. Korzhik and B. Mohar, Minimal obstructions for 1-immersions and hardness of 1-planarity test, Springer Lect. Notes Comput. Sci. 5417 (2009), 302-312, 2009.
[14]	T. Madaras and R. Skrekovski, Heavy paths, light stars and big melons, Discrete Math. 286 (2004), 115-131.
[15]	B. Mohar, R. Skrekovski and H.-J. Voss, Light subgraphs in planar graphs of minimum degree 4 and edge-degree 9, J. Graph Theory 44 (2003), 261-295.
[16]	G. Ringel, Ein sechsfarbenproblem auf der Kugel (in German), Abh. Math. Sem. Hamburg. Univ. 29 (1965), 107-117.
[17]	Y. Suzuki, Optimal 1-planar graphs which triangulate other surfaces, Discrete Math. 310 (2010), 6-11.
[18]	W. Wang and K.-W. Lih, Coupled choosability of plane graphs, J. Graph Theory 58 (2008), 27-44.
[19]	X. Zhang and G. Liu, On edge colorings of 1-planar graphs without chordal 5-cycles, Ars Combin. 104 (2012), 431-436.
[20]	X. Zhang and G. Liu, On edge colorings of 1-planar graphs without adjacent triangles, Inform. Process. Lett. 112 (2012), 138-142.
[21]	X. Zhang, G. Liu and J.-L. Wu, Edge coloring of triangle-free 1-planar graphs (in Chinese), Journal of Shandong University (Natural Science) 45 (2010), 15-17.
[22]	X. Zhang, G. Liu and J.-L. Wu, Structural properties of 1-planar graphs and an application to acyclic edge coloring (in Chinese), Scientia Sinica Mathematica 40 (2010), 1025-1032.
[23]	X. Zhang, G. Liu and J.-L. Wu, Light subgraphs in the family of 1-planar graphs with high minimum degree, ActaMath. Sinica, English Series 28 (2012), 1155-1168.
[24]	X. Zhang, G. Liu and J.-L. Wu, On the linear arboricity of 1-planar graphs, OR Transactions 15 (2011), 38-44.
[25]	X. Zhang and J.-L. Wu, Edge coloring of 1-planar graphs, Inform. Process. Lett. 111 (2011), 124-128.
[26]	X. Zhang X, 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. Theoret. Comp. Sc. 13 (2011), 9-16.
[27]	X. Zhang, J.-L. Wu, G. Liu, List edge and list total coloring of 1-planar graphs, Front. Math. China 7 (2012), 1005-1018.
[28]	X. Zhang, Y. Yu and G. Liu, On (p, 1)-total labelling of 1-planar graphs, Cent. Eur. J. Math. 9 (2011), 1424-1434.