Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 4 (2011) 245–254
On local properties of 1-planar graphs
with high minimum degree
Dávid Hudák , Tomáš Madaras ∗
Institute of Mathematics, Faculty of Sciences
University of P. J. Šafárik
Jesenná 5, 041 54 Košice, Slovak Republic
Received 10 December 2009, accepted 23 December 2010, published online 26 May 2011
Abstract
A graph is called 1-planar if there exists its drawing in the plane such that each edge
contains at most one crossing. We prove that each 1-planar graph of minimum degree 7
contains a pair of adjacent vertices of degree 7 as well as several small graphs whose ver-
tices have small degrees; we also prove the existence of a 4-cycle with relatively small
degree vertices in 1-planar graphs of minimum degree at least 6.
Keywords: 1-planar graph, light graph.
Math. Subj. Class.: 05C10
1 Introduction
Throughout this paper, we consider connected graphs without loops or multiple edges; we
use the standard graph terminology by [8].
A graphG is called planar if there exists its drawingD(G) in the plane such that no two
edges of D(G) have an internal point (a crossing) in common; the drawing D(G) with this
property is called a plane graph. Planar graphs are one of the most studied graph families,
possessing a wide variety of applications.
There are several different approaches generalizing the concept of planarity. One of
them allows, in a drawing of a graph, a constant number of crossings per edge. In particular,
if there exists a drawing D(G) of a graph G in the plane such that each edge of D(G)
contains at most one crossing, then G is called 1-planar. These graphs were introduced by
Ringel [19] in connection with the simultaneous vertex/face colouring of plane graphs (note
∗This work was supported by Science and Technology Assistance Agency under the contract No. APVV-0007-
07.
E-mail addresses: david.hudak@student.upjs.sk (Dávid Hudák), tomas.madaras@upjs.sk (Tomáš Madaras)
Copyright c© 2011 DMFA Slovenije
246 Ars Math. Contemp. 4 (2011) 245–254
that the graph of adjacency/incidence of vertices and faces of a plane graph is 1-planar);
in [19], it was proved that 1-planar graphs are 7-colourable (a linear 7-colouring algorithm
was presented in [7]), and Borodin ([1, 3]) proved Ringel’s conjecture that these graphs are
6-colourable.
Comparing to the family of planar graphs, the family of 1-planar graphs is still only
little explored (for example, except the above mentioned colouring results, there is only
one other paper [5] on acyclic colourings of 1-planar graphs). In general, 1-planar graphs
differ from planar ones in several fundamental aspects – they are not minor closed, their
recognition is NP-complete (see [16]) and, for sufficiently large n, there are exponentially
many nonisomorphic critical non-1-planar graphs on n vertices ([15, 16]).
On the other hand, concerning the local structure, 1-planar graphs show a similar be-
haviour as planar graphs. Recently, the local structure of these graphs was studied in [11],
[4], [12]; it was shown that, under certain conditions (like prescribed minimum degree or
girth), 1-planar graphs contain various small subgraphs whose vertices have small degrees
(that is, bounded above by a constant depending only on the type of the subgraph). In this
paper, we continue this research by studying the local properties of 1-planar graphs which
have (or are close to have) the maximum possible minimum degree (by [19], this value is
equal to 7). Our motivation comes from analogical results for planar graphs of minimum
degree 5 which contain a large variety of subgraphs with vertices of small degrees. For
example, Borodin in [2] proved that each planar graph of minimum degree 5 contains a 3-
cycle with the weight (that is, the sum of degrees of its vertices) at most 17; similar results
hold also for short cycles and stars (see [13, 6, 14, 17, 18]). Note that, for planar graphs of
minimum degree 4, analogical results do not hold (for details, see [9] and [10]). Therefore,
one may expect that, with the increasing minimum degree of a 1-planar graph, there will
appear many small subgraphs with similar properties.
In the following, let K∗2,3 denote a graph K2,3 with an extra edge between two vertices
of the smaller bipartition, and let W5 denote the 5-wheel (the 4-sided pyramid graph).
We prove
Theorem 1.1. Each 1-planar graph of minimum degree 7 contains
a) a pair of adjacent 7-vertices,
b) a copy of K4 with all vertices of degree at most 13,
c) a copy of K∗2,3 with all vertices of degree at most 13,
d) a copy of W5 with all vertices of degree at most 11.
In addition, we prove
Theorem 1.2. Each 1-planar graph of minimum degree 6 contains a copy of C4 with all
vertices of degree at most 47.
The proofs of all these results follow the same strategy – we assume the existence
of a hypothetical counterexample G to a particular theorem, and its 1-planar drawing
D = D(G). The drawing D is then transformed into asociated plane graph G× =
(V ×, E×, F×) of G in such a way that all crossings of D become new 4-vertices. These
4-vertices are called false, the vertices of G× which correspond to the original vertices of
D are called true; a face of G× is a false face if it is incident with at least one false vertex,
otherwise it is a true face. Next, we proceed by Discharging Method. Each vertex and
D. Hudák and T. Madaras: On local properties of 1-planar graphs. . . 247
each face of G× is assigned a quantity c called initial charge; this can be done in several
different ways, of which we use the following two ones:
c(v) = degG×(v)− 4 for each vertex v ∈ V ×,
c(α) = degG×(α)− 4 for each face α ∈ F×,
(1)
c(v) = degG×(v)− 6 for each vertex v ∈ V ×,
c(α) = 2 degG×(α)− 6 for each face α ∈ F×,
(2)
By Euler polyhedral formula, we obtain that, under the first initial charge assignment,∑
x∈V ×∪F×
c(x) = −8 (or -12 under the second assignment).
Next, the initial charges of elements of G× are locally redistributed in such a way
that the total sum of all charges remains the same (hence, negative). This redistribution is
performed by a set of discharging rules which specify the way of transfer of a charge from
one element to another one in specific configurations of vertices and faces of G×. Finally,
by a case analysis, it is shown that, after discharging, each element ofG× has a nonnegative
final charge c∗; thus, the total sum of final charges is also nonnegative, a contradiction.
For purposes of these proofs, we use more specialized notation. Given a d-vertex x
of G×, x1, . . . , xd will denote its neighbours in clockwise order. By fi, i = 1, . . . , d, we
denote the face of G× which contains the facial subwalk xixxi+1 (index modulo d). If fi
is a 3-face, then f ′i denotes a face having the common edge xixi+1 (index modulo d) with
fi; further, if f ′i is a 3-face, then its third vertex (which is different from xi and xi+1) will
be denoted by x′i.
2 Proofs
Proof of Theorem 1.1a). By contradiction. Suppose that there exists a 1-planar graph G
of minimum degree 7 such that each its 7-vertex is adjacent only with ≥ 8-vertices. We
proceed with the Discharging Method with the initial charge assignment (1); the initial
charges are redistributed according to the following rules:
Rule 1: Each ≥ 7-vertex v ∈ V × redistributes its initial charge uniformly among incident
3-faces.
Rule 2: Each 3-face with a positive charge after application of Rule 1 sends 37 to each
incident 7-vertex.
Rule 3: Each 7-vertex with a positive charge after application of Rules 1 and 2 redistributes
this charge uniformly among incident false 3-faces.
We check the nonnegativity of final charges of vertices and faces ofG×. Since false vertices
and ≥ 4-faces of G× are not influenced by discharging, their final charge is equal to the
initial one; hence, it is nonnegative. Also, from the formulation of discharging rules, it
is easy to see that the final charge of ≥ 7-vertices is nonnegative. Thus, it is enough to
analyze just the final charge of 3-faces; let α be a 3-face of G×.
Case 1: Let α be true and incident only with ≥ 8-vertices. Then, by Rule 1, c∗(α) ≥
−1 + 3 · 8−48 = −1 +
3
2 > 0.
Case 2: Let α be true and incident with exactly one 7-vertex. By Rules 1 and 2, c∗(α) ≥
−1 + 2 · 8−48 +
7−4
7 −
3
7 = 0.
(Note that after application of Rule 1, each true 3-face has a positive charge at least 37 .)
248 Ars Math. Contemp. 4 (2011) 245–254
Case 3: Let α = [xyz] be false with a false vertex x.
Case 3.1: If both y, z are≥ 8-vertices, then, by Rule 1, c∗(α) ≥ −1+2· 8−48 = −1+2·
1
2 =
0.
Case 3.2: Suppose that, without loss of generality, y is a 7-vertex and z is an ≥ 8-vertex.
If y is incident with an ≥ 4-face, then c∗(α) ≥ −1 + 7−47−1 +
8−4
8 = 0; similarly, if z is
incident with an ≥ 4-face, then c∗(α) ≥ −1 + 7−47 +
8−4
8−1 = 0. Hence, suppose that both
y, z are incident with 3-faces only. Then there exists a true 3-face incident with y, which
sends, by Rule 2, 37 to y. Then, by Rule 3, y sends at least
3
7
7−1 =
1
14 to α, and we obtain
c∗(α) ≥ −1 + 7−47 +
8−4
8 +
1
14 = 0.
Proof of Theorem 1.1b). By contradiction. Suppose that there exists a 1-planar graph G
of minimum degree 7 such that each its subgraph K4 contains at least one ≥ 14-vertex,
called big; vertices of degrees between 7 and 13 are called intermediate. We proceed
with the Discharging Method with the initial charge assignment (2); the initial charges are
redistributed according to following rules:
Rule 1: Each ≥ 4-face α ∈ F× redistributes its initial charge uniformly among incident
4-vertices.
Rule 2: Each intermediate vertex sends 17 to each adjacent 4-vertex.
Rule 3: Let [xyz] be a 3-face of G×, x be a 4-vertex and y be an intermediate vertex. Then
y sends additional 114 to x.
Rule 4: Each big vertex sends 47 to each adjacent 4-vertex.
Rule 5: Let [xyz] be a 3-face of G×, x be a 4-vertex and y be a big vertex. Then y sends
additional 27 to x.
We check the nonnegativity of final charges of vertices and faces of G×. From the formu-
lation of discharging rules, it is easy to see that the final charge of all faces is nonnegative.
Thus, it is enough to analyze just the final charge of vertices.
Case 1: Let x be a 4-vertex of G×. If x is incident with at least two ≥ 4-faces, then, by
Rule 1, c∗(x) ≥ −2 + 2 · 2·4−62 = −2 + 2 · 1 = 0. If x is incident with exactly one
≥ 4-face, then, by Rules 1, 2 and 3 (or, eventually, 1, 4 and 5) we obtain the estimation
c∗(x) ≥ −2 + 2·4−62 + 4 ·
1
7 + 6 ·
1
14 = 0. Finally, if x is incident only with 3-faces, then
its neighbours in G× induce a K4, hence, one of them is big; then, by Rules 2, 3, 4 and 5,
we obtain c∗(x) ≥ −2 + 3 · 17 + 6 ·
1
14 +
4
7 + 2 ·
2
7 = 0.
Case 2: Let x be an intermediate d-vertex of G×. Then c∗(x) ≥ d − 6 − d · 17 ≥ 0 for
d ≥ 7.
Case 3: Let x be a big d-vertex of G×. Then c∗(x) ≥ d− 6− d · 47 ≥ 0 for d ≥ 14.
Proof of Theorem 1.1c). By contradiction. Suppose that there exists a 1-planar graph G
of minimum degree 7 such that each its subgraph K∗2,3 contains at least one ≥ 14-vertex,
called big; vertices of degrees between 7 and 13 are called intermediate. We proceed
with the Discharging Method with the initial charge assignment (1); the initial charges are
redistributed according to following rules (the first four rules are applied in the first phase
of discharging):
D. Hudák and T. Madaras: On local properties of 1-planar graphs. . . 249
Rule 1: Each intermediate vertex sends 37 to each incident 3-face.
Rule 2: Let α = [xyz] be a 3-face of G×, β be an ≥ 4-face having the common edge xy
with α and let v be a true vertex of β which is incident to x or y. Then v sends 314 to α.
Rule 3: Each big vertex sends 47 to each incident 3-face.
Rule 4: Let α = [xyz], β = [yzv] be 3-faces of G× and v be a big vertex. Then v sends 17
to α.
Rule 5: Each 3-face with positive charge after application of Rules 1 – 4 redistributes this
charge uniformly among adjacent 3-faces that have negative charge after application of the
above-mentioned rules.
Rule 6: Each ≥ 5-face sends 15 to each adjacent 3-face.
We check the nonnegativity of final charges of vertices and faces of G×. Firstly, all false
vertices have nonnegative final charge as they are not involved in the discharging procedure.
For a 4-face α, c∗(α) = c(α) = 0; if α is an r-face of G× with r ≥ 5, then, by Rule 6,
c∗(α) ≥ r − 4− r · 15 =
4
5r − 4 ≥ 0.
Let v be an intermediate d-vertex of G×. Observe that, in Rule 2, v just further re-
distributes (potentially into two 314 ) the spared charge
3
7 (as Rule 1 is not applied in this
situation). Hence, c∗(v) ≥ d− 4− 37d ≥ 0 for d ≥ 7.
Let v be a big d-vertex and α be a face incident with v. If α is a 3-face, then both
Rule 3 and 4 may be involved with the total contribution 47 +
1
7 =
5
7 ; if α is an ≥ 4-face,
then Rule 2 is possibly applied with the total contribution 2 · 314 =
3
7 . We conclude that
the maximum charge transferred from v involving a face incident with v is 57 ; therefore,
c∗(v) ≥ d− 4− 57d ≥ 0 for d ≥ 14.
In the following, we analyze the final charge of 3-faces in more detail.
Case 1: Let a 3-face α be incident with a big vertex. Then at least one of the remaining
two vertices is true and, by Rules 3 and 1 or 3, c∗(α) ≥ −1 + 47 +
3
7 = 0.
Case 2: Let all vertices of a 3-face α be intermediate. Then c∗(α) ≥ −1 + 3 · 37 > 0.
Case 3: Let a 3-face α be incident with a false vertex c and two other vertices x, y; accord-
ing to Case 1, x, y are intermediate. Let α1, α2 and α3 be faces of G× incident with edges
xy, xc and yc, respectively.
Case 3.1: Let some of αi, i = 1, 2, 3 be an ≥ 4-face. If α2 or α3 is an ≥ 4-face, then,
by Rules 1 and 2, c∗(α) ≥ −1 + 2 · 37 +
3
14 =
1
14 > 0. If α1 is an ≥ 5-face, then,
by Rules 1 and 6, c∗(α) ≥ −1 + 2 · 37 +
1
5 =
2
35 > 0. Suppose that α1 is a 4-face.
Then there exists a true vertex on α1 that is incident to x or y; hence, by Rules 2 and 1,
c∗(α) ≥ −1 + 2 · 37 +
3
14 =
1
14 > 0.
Case 3.2: Let all αi, i = 1, 2, 3, be 3-faces. Denote α1 = [xyz1], α2 = [xcz2], α3 = [ycz3]
(observe that z2 and z3 are true vertices).
Case 3.2.1: Let z1 be a true vertex. Then at least one of z1, z2, z3 is big (to avoid a light
copy of K∗2,3); by Rules 1 and 4, we have c
∗(α) ≥ −1 + 2 · 37 +
1
7 = 0.
Case 3.2.2: Suppose that z1 is false; further, we can suppose that both z2, z3 are intermedi-
ate (otherwise we argue similarly as in the Case 3.2.1). Let β1, β2 be faces that are adjacent
to α1 through the edge xz1 and yz1, respectively. If both β1, β2 are ≥ 4-faces, then, by
Rules 1 and 2, the face α1 receives at least 2 · 37 + 2 ·
3
14 =
9
7 and (having initial charge
−1) keeps at least 27 . Since α is the only 3-face adjacent to α1, the face α1 sends at least
250 Ars Math. Contemp. 4 (2011) 245–254
2
7 to α by Rule 5, so that c
∗(α) ≥ −1 + 2 · 37 +
2
7 > 0. If exactly one of β1, β2, say
β1, is a 3-face, then its third vertex (different from x, z1) is big (otherwise we find a light
copy of K∗2,3). Using Rules 1, 4 and 2 (note that z1 is adjacent to a true vertex incident
with β2), we obtain that α1 receives at least 2 · 37 +
1
7 +
3
14 =
17
14 and (subtracting the
initial charge −1) keeps at least 314 . By Rule 5, this charge is sent to α, and so we obtain
c∗(α) ≥ −1+2 · 37 +
3
14 > 0. Finally, suppose that both β1, β2 are 3-faces. Then both these
faces are incident with big vertices and, by Rules 1 and 3, they receive at least 37 +
4
7 = 1;
we conclude that, after the first phase, β1 and β2 have nonnegative charge (hence, by Rule
5, α1 sends a charge to at most one 3-face). Using Rules 1 and 4, we obtain that, in the first
phase, α1 receives at least 2 · 37 + 2 ·
1
7 ; thus, by Rule 5, α1 may send at least
1
7 to α and
we have c∗(α) ≥ −1 + 2 · 37 +
1
7 = 0.
Proof of Theorem 1.1d). By contradiction. Suppose that there exists a 1-planar graph
G of minimum degree 7 such that each its subgraph W5 contains a big vertex of degree
at least 12. We proceed with the Discharging Method with the initial charge assignment
(1); the initial charges are redistributed according to following rules (which are applied
sequentially; by ci(x), we denote the charge of an element x ∈ V × ∪ F× after application
of the first i rules):
Rule 1: Each ≥ 7-vertex sends 49 to each incident false 3-face and
1
3 to each incident true
3-face.
Let k(v) be the number of false 3-faces incident with a vertex v.
Rule 2: If v is a vertex of G× with c1(v) ≥ 118k(v), then v sends
1
18 to each incident false
3-face; if c1(v) < 118k(v) or k(v) = 0, no charge is transferred.
Let n(v) be the number of 3-faces [xyz] such that x is a 7-vertex and y is a false vertex
of G× (such faces will be called awkward).
Rule 3: If v is a non-big vertex of G× with c2(v) > 0, then v shares its charge equally
among all incident awkward faces; further, if c2(v) ≥ 118n(v), then v sends
1
18 to each
incident awkward face.
Rule 4: Each big vertex sends 13 to each adjacent 7-vertex.
Rule 5: If a 7-vertex v has received a contribution from a big vertex, then this contribution
is further redistributed equally among all false 3-faces incident with v.
We check the nonnegativity of final charges of vertices and faces of G×. As ≥ 4-faces
and 4-vertices are not influenced by the discharging, it is enough to analyze 3-faces and
≥ 7-vertices of G×.
Case 1: Let α = [xyz] be a 3-face.
Case 1.1: If α is a true 3-face, then, by Rule 1, c∗(α) = c1(α) ≥ −1 + 3 · 13 = 0.
Case 1.2: Suppose that α is a non-awkward false 3-face and z is its false vertex. Let x be
a d-vertex, d ≥ 8. Then c1(x) ≥ d − 4 − d · 49 =
5
9d − 4 ≥
1
18d. Thus c1(x) ≥
1
18k(x)
and, by Rule 2, x sends 118 to α. The same consideration applies to y; hence, we obtain that
c∗(α) ≥ −1 + 2 · 49 + 2 ·
1
18 = 0.
Case 1.3: Let α be an awkward face with 7-vertex x.
D. Hudák and T. Madaras: On local properties of 1-planar graphs. . . 251
Case 1.3.1: Let y be a big d-vertex. Then c1(y) ≥ d− 4− 49d =
5
9d− 4 ≥
1
18d ≥
1
18k(y);
hence, by Rule 2, y sends 118 to α. Further, x receives
1
3 from y by Rule 4. By parity
argument, k(x) ≤ 6, and x sends, by Rule 5, at least 16 ·
1
3 =
1
18 to each incident false
3-face. Therefore, we obtain c∗(α) ≥ −1 + 2 · 49 +
1
18 +
1
18 = 0.
Case 1.3.2: Let y be a d-vertex with d ∈ {9, 10, 11}. Note that c1(y) ≥ 118k(y) and y
sends 118 to α by Rule 2. Further, c2(y) ≥ d− 4− k(y) ·
4
9 − (d− k(y)) ·
1
3 − n(y) ·
1
18 =
2
3d−4−
1
9k(y)−
1
18n(y) ≥
2
3d−4−
1
9k(y)−
1
18k(y) =
2
3d−4−
3
18k(y) ≥
2
3d−4−
3
18d =
9
18d− 4 ≥
1
18d for d ≥ 9. This implies that y sends additional
1
18 to α by Rule 3; in total,
we obtain c∗(α) ≥ −1 + 2 · 49 +
1
18 +
1
18 = 0.
Case 1.3.3: Let y be an 8-vertex. Still, y sends 118 to α by Rule 2. Suppose first that x is
incident with at least one ≥ 4-face. Then c1(x) ≥ 7 − 4 − 6 · 49 =
3
9 =
1
18 · 6; hence, x
may send 118 to α by Rule 2. Now, let x be incident only with 3-faces; note that, in this
case, the number of false 3-faces containing x is even. If at least three of them are true
3-faces, then c1(x) ≥ 7 − 4 − 4 · 49 − 3 ·
1
3 =
2
9 = (7 − 3) ·
1
18 and again, x can send
1
18 to α by Rule 2. So suppose that there is exactly one true 3-face incident with x. Then
x and its four true neighbours induce a copy of W5 in G. Thus, at least one of neighbours
of x is big and sends, by Rule 4, 13 to x; by Rule 5, this charge is equally redistributed
among six false 3-faces incident with x, which yields the contribution 118 to α, and so
c∗(α) ≥ −1 + 2 · 49 +
1
18 +
1
18 = 0.
Case 1.3.4: Let y be a 7-vertex. Then we may use the arguments from Case 1.3.3 con-
cluding that each of x, y sends 118 to α either by Rule 2 or by Rule 5. Hence, we have
c∗(α) ≥ −1 + 2 · 49 + 2 ·
1
18 = 0.
Case 2: Let x be a non-big d-vertex. Note that transfers from x by Rules 2, 3 or 5 are
performed only if x has sufficient charge after application of Rule 1; after these subsequent
transfers, x is discharged to 0. Hence, it is enough to check the situation after using the Rule
1. Let t be number of transfers of 49 by Rule 1 from x to incident false 3-faces, and q the
number of transfers of 13 from x to other incident 3-faces. Then t+ q ≤ d and t ≤ 2 ·
⌊
d
2
⌋
,
and we obtain c1(x) ≥ d−4− 49 t−
1
3q = d−4−
1
3 (t+q)−
1
9 t ≥ d−4−
1
3d−
1
9 ·2·
⌊
d
2
⌋
≥ 0
for d ≥ 7.
Case 3: Let x be a big d-vertex. Let n and p be numbers of false and true 3-faces incident
with x and s be the number of 7-vertices adjacent to x. Then p + n ≤ d and s ≤ d;
moreover, since each pair of false 3-faces in the neighbourhood of x contains at least one
vertex of degree 6= 7, it follows that p + n + s ≤ 2d − n2 . Then, by Rules 1, 2 and 4, we
obtain the estimation c∗(x) ≥ d − 4 − 49n −
1
3p −
1
18n −
1
3s = d − 4 −
n
2 −
p
3 −
s
3 ≥
d− 4− 23d =
d
3 − 4 ≥ 0 for d ≥ 12.
Proof of Theorem 1.2. By contradiction. Suppose that there exists a 1-planar graph G of
minimum degree 6 such that each its 4-cycle contains a big vertex of degree at least 48.
We proceed with the Discharging Method with the initial charge assignment (2); the initial
charges are redistributed according to the following rules :
Rule 1: Each big face sends 12 to each incident 4-vertex.
Rule 2: Let β = [xyz] be a 3-face having the common edge yz with a big face α, and let
x be a 4-vertex. Then α sends 14 to x.
252 Ars Math. Contemp. 4 (2011) 245–254
Rule 3: Let β = [xyz] be a 3-face having the common edge xy with a big face α, and let
x be a 4-vertex. Then α sends 18 to x.
Rule 4: Let β = [xyz] be a 3-face adjacent with a 3-face γ = [yzw] that has a common
edge zw with a big face α, and let x be a 4-vertex. Then α sends 18 to x.
Rule 5: Let α, β be two incident big faces with the common edge xy, and let x be a
4-vertex. Then α sends 14 to x.
Rule 6: Let y be a big vertex adjacent to an 4-vertex x. Then y sends 58 to x.
Rule 7: Let α = [xyz] be a 3-face, y be big, and x be a 4-vertex. Then y sends additional
5
16 to x.
Rule 8: Let α = [xyz], β = [yzw] be 3-faces, w be big, and x be a 4-vertex. Then w sends
1
4 to x.
Rule 9: Let α = [xyz], β = [xyw] be 3-faces, w be big, and x be a 4-vertex. Then w sends
additional 18 to x.
Rule 10: Let α = [xyz] be a 3-face having a common edge xy with a big face β, z be big,
and x be a 4-vertex. Then z sends additional 14 to x.
Rule 11: Let α = [xyz], β = [yzv], and γ = [yvw] be 3-faces, w be big, and x be a
4-vertex. Then w sends additonal 18 to x.
We will analyze the final charges of vertices and faces of G×.
Case 1: Let x be a 4-vertex.
Case 1.1: If all fi, i = 1, . . . , 4 are big, then, by Rule 1, c∗(x) ≥ −2 + 4 · 12 = 0.
Case 1.2: Let exactly one of fi, say f4, be a 3-face. Then c∗(x) ≥ −2+3· 12+2·
1
8+4·
1
4 =
3
4 > 0 by Rules 1 (applied three times), 3 (twice), and 5 (four times).
Case 1.3: Let two of fi, i = 1, . . . , 4 be 3-faces. According to the symmetry, we distin-
guish two cases:
Case 1.3.1: Let f2,f4 be 3-faces. Then one of xi, say x1, is big (otherwise x1x3x2x4
is a light 4-cycle). By Rules 1 (twice), 3 (four times), 6 (once) and 7 (once), c∗(x) ≥
−2 + 2 · 12 + 4 ·
1
8 +
5
8 +
5
16 > 0.
Case 1.3.2: Let f1, f4 be 3-faces. If one of x1,. . . ,x4 is big, then c∗(x) ≥ −2 + 2 · 12 + 2 ·
1
8 + 2 ·
1
4 +
5
8 > 0 by Rules 1 (applied twice), 3 (twice), 5 (twice), and 6 (once).
So, assume that no neighbour of x is big. Consider the face f ′1. If f
′
1 is big, then it
sends 14 to x by Rule 2; otherwise it is a 3-face. If x
′
1 is a true vertex, then it must be
big (otherwise x1x′1x2x4 is a light 4-cycle). The big vertex x
′
1 sends
1
4 to x by Rule 8. It
remains to resolve the case when f ′1 is a 3-face, but x
′
1 is a false vertex. Then consider the
faces f ′l1 , f
′r
1 that share with f
′
1 common edge x
′
1x1 or x
′
1x2, respectively. If some of them
is a 3-face, then its third vertex z 6= x′1, x1 (or z 6= x′1, x2) must be big (otherwise x4x1zx2
is a light 4-cycle). Hence, it contributes 18 to x by Rule 11. If some of these faces is big,
then it sends 18 to x by Rule 4. Consequently, x receives ≥
1
4 due to the transfers through
edge x1x2. The same consideration is applied on the transfers through edge x4x1. Thus,
we obtain c∗(x) ≥ −2 + 2 · 12 + 2
1
8 + 2 ·
1
4 + 2 ·
1
4 =
1
4 > 0.
Case 1.4: Let three of fi, say f1, f2, and f4, be 3-faces. Note that at least one of neighbours
of x is big.
Case 1.4.1: If x has at least two big neighbours, then c∗(x) ≥ −2 + 12 + 2 ·
1
8 + 2 ·
5
8 + 2 ·
5
16 +2 ·
1
8 > 0 by Rules 1 (applied once), 3 (twice), 6 (at least twice), 7 (at least twice) and
9 (at least twice).
D. Hudák and T. Madaras: On local properties of 1-planar graphs. . . 253
Case 1.4.2: Let x have exactly one big neighbour. If x1 or x2 is big, then c∗(x) ≥ −2 +
1
2 +2 ·
1
8 +
5
8 +2 ·
5
16 +
1
8 +
1
4 > 0 by Rules 1 (applied once), 3 (twice), 6 (once), 7 (twice),
9 (once) and 10 (once).
Suppose, without loss of generality, that x3 is big. Consider now the faces f ′1, f
′
4. We
may use the same argumentation as in Case 1.3.2. The transfer through edges x1x2 and
x1x4 is always at least 2 · 14 . Thus, in total, c
∗(x) ≥ −2+ 12 +2 ·
1
8 +
5
8 +
5
16 +
1
8 +2 ·
1
4 > 0
by Rules 1 (applied once), 3 (twice), 6 (once), 7 (once), 9 (once), and the above mentioned
contribution.
Case 1.5: Let all faces incident with x be 3-faces. Note that at least one of neighbours of x
is big. If at least two neighbours of x are big, then c∗(x) ≥ −2+ 2 · 58 +4 ·
5
16 +2 ·
1
8 > 0
by Rules 6 (twice), 7 (four times) and 9 (four times). Let exactly one of neighbours of x,
say x1, be big. Then, using the same argumentation as in Case 1.3.2, x receives at least
2 · 14 through edges x2x3 and x3x4. In total, c
∗(x) ≥ −2 + 58 + 2 ·
5
16 + 2 ·
1
8 +
1
2 = 0 by
Rules 6 (applied once), 7 (twice), 9 (twice), and the above mentioned contribution.
Case 2: Let α be a big face. Observe that Rules 3, 4 just halve the charge 14 that is saved
(since, in situation of Rules 3, 4, there is no such transfer as in Rule 2). Also, in Rule 5,
the full transfer of 14 is saved, because the situation of Rules 3 and 4 is not involved in this
rule. Hence, we may roughly consider that, through each edge incident with α, 14 of charge
is transfered. Also, note that Rule 1 applies to at most bdeg(α)2 c vertices incident with α.
Therefore, c∗(α) ≥ c(α)−bdeg(α)2 c ·
1
2 −deg(α) ·
1
4 ≥ 2 ·deg(α)−6−
deg(α)
4 −
deg(α)
4 =
3
2 · deg(α)− 6 ≥ 0 if deg(α) ≥ 4.
Case 3: Let x be a big vertex. Note that Rule 7 just halves the charge that is saved in
the corresponding situation when Rule 6 is not used, Rules 9, 11 work in the same way in
connection with Rule 8. The Rule 10 sends the full charge that was saved in Rule 8. We can
use very rough estimation 58 +
1
4 for a charge assigned to a neighbour of x, and to an edge
of a 3-face incident with x. By this rough estimation, c∗(x) ≥ c(x)− ( 58 +
1
4 ) · deg(x) =
deg(x)− 6− 78 · deg(x) =
1
8 · deg(x)− 6 ≥ 0 for deg(x) ≥ 48.
References
[1] O. V. Borodin, Solution of the Ringel problems on the vertex-face coloring of plane graphs
and the coloring of 1-planar graphs, Metody Diskretn. Anal. 41 (1984), 12–26.
[2] O. V. Borodin, Solution of Kotzig-Grünbaum problems on separation of a cycle in planar
graphs, Mat. Zametki 46 (1989), 9–12, (in Russian).
[3] O. V. Borodin, A new proof of 6 color theorem, J. Graph Theory 19 (1995), 507–521.
[4] O. V. Borodin, I. G. Dmitriev and A. O. Ivanova, The height of a cycle in 1-planar graphs
with minimum degree 5 without triangles, Diskretn. Anal. Issled. Oper. 15 (2008), 11–16, (in
Russian).
[5] O. V. Borodin, A. V. Kostochka, A. Raspaud and E. Sopena, Acyclic colouring of 1-planar
graphs, Discrete Appl. Math. 114 (2001), 29–41.
[6] O. V. Borodin and D. Woodall, Short cycles of low weight in normal plane maps with mini-
mum degree 5, Discussiones Math. Graph Th. 16 (1998), 159–164.
[7] Z.-Z. Chen and M. Kouno, A linear-time algorithm for 7-coloring 1-plane graphs, Algorith-
mica 43 (2005), 147–177.
254 Ars Math. Contemp. 4 (2011) 245–254
[8] R. Diestel, Graph theory, Springer 2006.
[9] I. Fabrici, E. Hexel, S. Jendrol’ and H. Walther, On vertex-degree restricted paths in polyhe-
dral graphs, Discrete Math. 212 (2000), 61–73.
[10] I. Fabrici and S. Jendrol’, Subgraphs with restricted degrees of their vertices in planar 3-
connected graphs, Graphs and Combin. 13 (1997), 245–250.
[11] I. Fabrici and T. Madaras, The structure of 1-planar graphs, Discrete Math. 307 (2007), 854–
865.
[12] D. Hudák and T. Madaras, On local structure of 1-planar graphs of minimum degree 5 and
girth 4, Discussiones Math. Graph. Th. 29 (2009), 385–400.
[13] S. Jendrol’ and T. Madaras, On light subgraphs in plane graphs of minimum degree five,
Discussiones Math. Graph Th. 16 (1996), 207–217.
[14] S. Jendrol’, T. Madaras, R. Soták and Z. Tuza, On light cycles in plane triangulations, Discrete
Math. 197/198 (1999), 453–467.
[15] V. P. Korzhik, Minimal non-1-planar graphs, Discrete Math. 308 No. 7 (2008), 1319–1327.
[16] V. P. Korzhik and B. Mohar, Minimal obstructions for 1-immersions and hardness of 1-
planarity testing, Springer Lecture Notes in Computer Science 5417 (2009), 302–312.
[17] T. Madaras, R. Škrekovski and H.-J. Voss, The 7-cycle C7 is light in the family of all plane
graphs with minimum degree 5, Discrete Math. 307 (2007), 1430–1435.
[18] B. Mohar, R. Škrekovski and H.-J. Voss, Light subgraphs in planar graphs of minimum degree
4 and edge degree 9, J. Graph Theory 44 (2003), 261–295.
[19] G. Ringel, Ein Sechsfarbenproblem auf der Kugel, Abh. Math. Sem. Univ. Hamburg 29 (1965),
107–117.