# On $2$-distance $16$-coloring of planar graphs with maximum degree at most
five

Zakir Deniz  Department of Mathematics, Duzce University, Duzce, 81620,
Turkey<EMAIL_ADDRESS>
###### Abstract.

A vertex coloring of a graph $G$ is called a 2-distance coloring if any two
vertices at a distance at most $2$ from each other receive different colors.
Suppose that $G$ is a planar graph with a maximum degree at most $5$. We prove
that $G$ admits a $2$-distance $16$ coloring, which improves the result given
by Hou et al. (Graphs and Combinatorics 39:20, 2023).

###### Key words and phrases:

Coloring, 2-distance coloring, girth, planar graph.

The author is supported by TÜBİTAK, grant no:122F250

##  1\. Introduction

We consider only finite simple graphs throughout this paper, and refer to [10]
for terminology and notation not defined here. Let $G$ be a graph, we use
$V(G),E(G),F(G),$ and $\Delta(G)$ to denote the vertex, edge and face set, and
the maximum degree of $G$, respectively. If there is no confusion in the
context, we abbreviate $\Delta(G)$ to $\Delta$. A 2-distance coloring is a
proper vertex coloring where two vertices that are adjacent or have a common
neighbour receive different colors, and the smallest number of colors for
which $G$ admits a 2-distance coloring is known as the 2-distance chromatic
number $\chi_{2}(G)$ of $G$. In [4], Cranston has provided a comprehensive
survey on 2-distance coloring and related coloring concepts.

In 1977, Wegner [9] posed the following conjecture.

######  Conjecture 1.1.

For every planar graph $G$, $\chi_{2}(G)\leq 7$ if $\Delta=3$,
$\chi_{2}(G)\leq\Delta+5$ if $4\leq\Delta\leq 7$, and
$\chi_{2}(G)\leq\big{\lfloor}\frac{3\Delta}{2}\big{\rfloor}+1$ if $\Delta\geq
8$,

Thomassen [8] (independently by Hartke et al. [5]) proved the conjecture for
planar graphs with $\Delta=3$, by showing that the square of every cubic
planar graph is 7-colorable. For general planar graphs, van den Heuvel and
McGuinness [6] showed that $\chi_{2}(G)\leq 2\Delta+25$, while the bound
$\chi_{2}(G)\leq\big{\lceil}\frac{5\Delta}{3}\big{\rceil}+78$ was proved by
Molloy and Salavatipour [7].

The conjecture remains open, even for small $\Delta$. Zhu [11] proved that
$\chi_{2}(G)\leq 13$ for planar graph with $\Delta=4$. On the other hand, Zhu
and Bu [12] showed that $\chi_{2}(G)\leq 20$ for planar graph with maximum
degree $\Delta\leq 5$. This bound was later reduced to $19$ by Chen et al.
[3], and to 18 by Hou et al. [2]. Recently, Aoki [1] and Zou et al. [13]
(independently) in unpublished papers have proved that $\chi_{2}(G)\leq 17$.
In this paper, we further improve the current bound by reducing it by one.

######  Theorem 1.2.

If $G$ is a planar graph with maximum degree at most $5$, then
$\chi_{2}(G)\leq 16$.

Given a planar graph $G$, we denote by $\ell(f)$ the length of a face $f$ and
by $d(v)$ the degree of a vertex $v$. A $k$-vertex is a vertex of degree $k$.
A $k^{-}$-vertex is a vertex of degree at most $k$ while a $k^{+}$-vertex is a
vertex of degree at least $k$. A $k$ ($k^{-}$ or $k^{+}$)-face is defined
similarly. A vertex $u\in N(v)$ is called $k$-neighbour (resp.
$k^{-}$-neighbour, $k^{+}$-neighbour) of $v$ if $d(u)=k$ (resp. $d(u)\leq k$,
$d(u)\geq k$). For a vertex $v\in V(G)$, we use $n_{i}(v)$ to denote the
number of $i$-vertices adjacent to $v$. We denote by $d(u,v)$ the distance
between $u$ and $v$ for any pair $u,v\in V(G)$. Also, we set $N_{i}(v)=\\{u\in
V(G)\ |\ 1\leq d(u,v)\leq i\\}$ for $i\geq 1$, so $N_{1}(v)=N(v)$ and let
$d_{2}(v);=|N_{2}(v)|$.

For $v\in V(G)$, we use $m_{k}(v)$ to denote the number of $k$-faces incident
with $v$. An $(x_{1},x_{2},\ldots,x_{k})$-face is a $k$-face with vertices of
degrees $x_{1},x_{2},\ldots,x_{k}$. Two faces $f_{1}$ and $f_{2}$ are called
adjacent if they share a common edge.

##  2\. The Proof of Theorem 1.2

###  2.1. The Structure of Minimum Counterexample

Let $G$ be a minimal counterexample to Theorem 1.2 such that $|V(G)+|E(G)|$ is
minimum. So, $G$ does not admit any $2$-distance $16$-coloring, but any planar
graph $G^{\prime}$ obtained from $G$ with smaller
$|V(G^{\prime})+|E(G^{\prime})|$ admits a 2-distance 16-coloring. Obviously,
$G$ is a connected graph.

We call a graph $H$ _proper_ with respect to $G$ if $H$ is obtained from $G$
by deleting some edges or vertices and adding some edges, ensuring that for
every pair of vertices $x_{1}$ and $x_{2}$ in $V(G)\cap V(H)$ having distance
at most 2 in $G$, they also have distance at most $2$ in $H$. If $f$ is a
2-distance coloring of such a graph $H$, then $f$ can be extended to the whole
graph $G$, provided that each of the remaining uncolored vertices has an
available color.

First, we present some structural results and forbidden configurations for the
graph $G$. The proofs of the following lemmas are quite similar: Given a
vertex $v\in V(G)$, we construct a graph $H$ by considering the vertices
$V(G-v)$ in such a way that $H$ is proper with respect to $G$. When we have a
$2$-distance $16$-coloring of $H$, we demonstrate that such a coloring can
always be extended to the entire graph $G$ by assigning a color to the removed
vertex $v$ when $d_{2}(v)\leq 15$.

######  Lemma 2.1.

For the graph $G$, we have $\delta(G)\geq 3$.

###### Proof.

Assume that $v$ is a $1$-vertex in $G$. By minimality, the graph $G-v$ has a
2-distance coloring $f$ with $16$ colors. Since $v$ has an available color,
the coloring $f$ can be extended to the whole graph $G$, a contradiction.

We next assume that $v$ is a $2$-vertex in $G$. Denote by $x,y$ the neighbours
of $v$, and let $G^{\prime}=G-v+xy$. By minimality, the graph $G^{\prime}$ has
a 2-distance coloring $f$ with $16$ colors. Notice that every vertex in
$V(G)$, except $v$, is colored by the same color appears on the same vertex in
$G^{\prime}$. Thus, it suffices to color only $v$. Since $d_{2}(v)\leq 10$,
i.e., $v$ has at most $10$ forbidden colors, we can color $v$ with an
available color, a contradiction. Hence, $G$ has no $1$-vertex and $2$-vertex.
∎

######  Lemma 2.2.

A $3$-vertex cannot be adjacent to any $4^{-}$-vertex.

###### Proof.

Let $v$ be a $3$-vertex with $N(v)=\\{v_{1},v_{2},v_{3}\\}$. Assume for a
contradiction that $v_{1}$ is a $4^{-}$-vertex. Let
$G^{\prime}=G-v+\\{v_{1}v_{2},v_{1}v_{3}\\}$. By minimality, the graph
$G^{\prime}$ has a 2-distance coloring $f$ with $16$ colors. Observe that
every vertex in $V(G)$, except $v$, is colored with the same color that
appears on the same vertex in $G^{\prime}$. Namely, $G^{\prime}$ is proper
with respect to $G$. Since $d(v_{1})+d(v_{2})+d(v_{3})\leq 14$, $v$ has at
most $14$ forbidden colors, and so we can color $v$ with an available color, a
contradiction. ∎

The following is an immediate consequence of Lemma 2.2.

######  Corollary 2.3.

Let $f$ be a $5$-face in $G$. Then,

  * $(a)$

there are at most two $3$-vertices on $f$,

  * $(b)$

if $f$ is incident to two $3$-vertices, then the other vertices on $f$ are
$5$-vertices,

  * $(c)$

if $f$ is incident to exactly one $3$-vertex, then $f$ is incident to at most
two $4$-vertices.

######  Corollary 2.4.

A $5^{+}$-face $f$ is incident to at most
$\big{\lfloor}\frac{\ell(f)}{2}\big{\rfloor}$ $3$-vertices.

We will now show that a $3$-face does not contain any $3$-vertices, which will
be useful throughout the paper.

######  Lemma 2.5.

If $v$ is a $3$-vertex, then $m_{3}(v)=0$ and $m_{4}(v)\leq 1$.

###### Proof.

Let $v$ be a $3$-vertex in the graph $G$, and let $v_{1},v_{2},v_{3}$ be the
neighbours of $v$. Assume that $v$ is incident to a $3$-face $f$, say
$f=v_{1}vv_{2}$. Let $G^{\prime}=G-v+v_{2}v_{3}$. By minimality, the graph
$G^{\prime}$ has a 2-distance coloring $f$ with $16$ colors. Observe that
every vertex in $V(G)$, except $v$, is colored by the same color appears on
the same vertex in $G^{\prime}$. Since $d_{2}(v)\leq 13$, we can color $v$
with an available color, a contradiction. Hence, $m_{3}(v)=0$.

We next assume that $v$ is incident to at least two $4$-faces $f_{1},f_{2}$,
say $f_{1}=v_{1}vv_{2}x$ and $f_{2}=v_{2}vv_{3}y$ for $x,y\in N(v_{2})$. Let
$G^{\prime}=G-v+v_{1}v_{3}$ (if $v_{1}v_{3}\notin E(G)$). Then $G^{\prime}$ is
proper with respect to $G$. Similarly as above, we get a contradiction since
$d_{2}(v)\leq 13$. Thus, $m_{4}(v)\leq 1$. ∎

We now turn our attention into the possible faces incident to a $4$-vertex
$v$, where we assume that $v_{1},v_{2},v_{3},v_{4}$ are the neighbours of $v$
in clockwise order.

######  Lemma 2.6.

Let $v$ be a $4$-vertex. Then $m_{3}(v)\leq 2$. In particular, if
$m_{3}(v)=2$, then $m_{4}(v)=0$ and $n_{5}(v)=4$.

###### Proof.

Assume that $v$ is incident to three $3$-faces $f_{1}=v_{1}vv_{2}$,
$f_{2}=v_{2}vv_{3}$, $f_{3}=v_{3}vv_{4}$. Clearly, we have $d_{2}(v)\leq 14$.
If we set $G^{\prime}=G-v+v_{1}v_{4}$, then $G^{\prime}$ is proper with
respect to $G$. By minimality, the graph $G^{\prime}$ has a 2-distance
coloring $f$ with $16$ colors. Since $d_{2}(v)\leq 14$, we can color $v$ with
an available color, a contradiction. Hence, $m_{3}(v)\leq 2$.

Suppose further that $m_{3}(v)=2$, and let $f_{1},f_{2}$ be $3$-faces incident
to $v$. We first show that $m_{4}(v)=0$. By contradiction, assume that $v$ is
incident to a $4$-face, say $f_{3}=v_{1}vv_{2}x$ for $x\in N(v_{1})\cap
N(v_{2})$. Notice that $f_{1},f_{2}$ can be adjacent or not. If $f_{1}$ and
$f_{2}$ are adjacent, say $f_{1}=v_{2}vv_{3}$ and $f_{2}=v_{3}vv_{4}$, then we
set $G^{\prime}=G-v+v_{1}v_{4}$. If $f_{1}$ and $f_{2}$ are non-adjacent, say
$f_{1}=v_{2}vv_{3}$ and $f_{2}=v_{4}vv_{1}$, then we set
$G^{\prime}=G-v+v_{3}v_{4}$. In both cases, we have $d_{2}(v)\leq 15$, and
$G^{\prime}$ is proper with respect to $G$. Similarly as above, we get a
contradiction. Thus, $m_{4}(v)=0$. We now show that all neighbours of $v$ are
$5$-vertices. By Lemma 2.2, all of them are $4^{+}$-vertices. Assume to the
contrary that there exists $v_{i}\in N(v)$ such that it is a $4$-vertex. If
$f_{1}$ and $f_{2}$ are adjacent, say $f_{1}=v_{1}vv_{2}$ and
$f_{2}=v_{2}vv_{3}$, then we set $G^{\prime}=G-v+v_{2}v_{4}$. If $f_{1}$ and
$f_{2}$ are non-adjacent, say $f_{1}=v_{1}vv_{2}$ and $f_{2}=v_{3}vv_{4}$,
then we set $G^{\prime}=G-v+\\{v_{2}v_{3},v_{1}v_{4}\\}$. In both cases, we
have $d_{2}(v)\leq 15$, and $G^{\prime}$ is proper with respect to $G$.
Similarly as above, we get a contradiction. Thus, $n_{5}(v)=4$. ∎

######  Proposition 2.7.

Let $v$ be a $4$-vertex with $m_{4}(v)=2$ and $n_{5}(v)=4$. If $v$ is incident
to two adjacent faces $f_{1},f_{2}$ such that $f_{1}$ (resp. $f_{2}$) is a
$3$-face (resp. $5^{+}$-face), then no edge in $G[N(v)]$ is contained in two
$3$-faces of $G$.

###### Proof.

Let $v$ be a $4$-vertex with $m_{4}(v)=2$ and $n_{5}(v)=4$. Suppose that $v$
is incident to both a $3$-face $f_{1}$ and a $5^{+}$-face $f_{2}$. Let $f_{1}$
and $f_{2}$ be adjacent. Without loss of generality, we may write
$f_{1}=v_{1}vv_{2}$. Obviously, $v_{1}v_{2}$ is the unique edge in $G[N(v)]$
since $m_{4}(v)=2$ and $m_{5}(v)=1$. Assume for a contradiction that
$v_{1}v_{2}$ is contained in two $3$-faces. Then we have $d_{2}(v)\leq 15$.
Since $f_{1}$ and $f_{2}$ are adjacent, and $v$ is incident to two $4$-faces,
there exists a common neighbour of $v_{3}$ and $v_{4}$ in $G-v$. If we set
$G^{\prime}=G-v+\\{v_{1}v_{4},v_{2}v_{3}\\}$, then $G^{\prime}$ is proper with
respect to $G$. By minimality, the graph $G^{\prime}$ has a 2-distance
coloring $f$ with $16$ colors. Since $d_{2}(v)\leq 15$, we can color $v$ with
an available color, a contradiction. ∎

######  Proposition 2.8.

Let $v$ be a $4$-vertex with $m_{3}(v)=2$. Then no edge in $G[N(v)]$ is
contained in two $3$-faces of $G$.

###### Proof.

Let $v$ be a $4$-vertex with $m_{3}(v)=2$. All $v_{i}$’s are $5$-vertices by
Lemma 2.6. Let $f_{1}$ and $f_{2}$ be $3$-faces incident to $v$ such that
$f_{1}=v_{i}vv_{i+1}$ and $f_{2}=v_{j}vv_{j+1}$ for $i,j\in[3]$. Assume for a
contradiction that $v_{i}v_{i+1}$ is contained in two $3$-faces. Then we have
$d_{2}(v)\leq 15$. If $f_{1}$ and $f_{2}$ are adjacent, say $i=1$ and $j=2$,
then we set $G^{\prime}=G-v+v_{2}v_{4}$. If $f_{2}$ and $f_{3}$ are non-
adjacent, say $i=1$ and $j=3$, then we set
$G^{\prime}=G-v+\\{v_{1}v_{4},v_{2}v_{3}\\}$. In both cases, $G^{\prime}$ is
proper with respect to $G$. By minimality, the graph $G^{\prime}$ has a
2-distance coloring $f$ with $16$ colors. Since $v$ has at most $15$ forbidden
colors, we can color $v$ with an available color, a contradiction. ∎

######  Lemma 2.9.

If $v$ is a $4$-vertex and incident to a $(4,4,4^{+})$-face, then $v$ is
incident to two $5^{+}$-faces.

###### Proof.

Let $v$ be a $4$-vertex, and suppose that $f$ is a $(4,4,4^{+})$-face so that
$f=v_{1}vv_{2}$ with $d(v_{1})=4$ and $d(v_{2})\geq 4$. By contradiction,
assume that $v$ is incident to at most one $5^{+}$-faces. We then deduce that
$v$ is incident to three $4^{-}$-faces, which implies that $d_{2}(v)\leq 15$.
In such a case, we set $G^{\prime}=G-v+\\{v_{1}v_{3},v_{1}v_{4}\\}$ (if
$v_{1}v_{3},v_{1}v_{4}\notin E(G)$). By minimality, the graph $G^{\prime}$ has
a 2-distance coloring $f$ with $16$ colors. Clearly, $G^{\prime}$ is proper
with respect to $G$. Because of $d_{2}(v)\leq 15$, we can color $v$ with an
available color, a contradiction. ∎

######  Lemma 2.10.

If $v$ is a $4$-vertex and incident to a $(4,5,5)$-face, then $v$ is incident
to a $5^{+}$-face.

###### Proof.

Let $v$ be a $4$-vertex, and suppose that $f$ is a $(4,5,5)$-face so that
$f=v_{1}vv_{2}$ with $d(v_{1})=d(v_{2})=5$. Assume for a contradiction that
$v$ is not incident to any $5^{+}$-face, i.e., all faces incident to $v$ are
$4^{-}$-faces, which implies that $d_{2}(v)\leq 15$. Let
$G^{\prime}=G-v+\\{v_{1}v_{4},v_{2}v_{3}\\}$ (if $v_{1}v_{4},v_{2}v_{3}\notin
E(G)$). By minimality, the graph $G^{\prime}$ has a 2-distance coloring $f$
with $16$ colors. Clearly, $G^{\prime}$ is proper with respect to $G$. Since
$v$ has at most $15$ forbidden colors, we can color $v$ with an available
color, a contradiction. Thus, $v$ is incident to a $5^{+}$-face. ∎

######  Proposition 2.11.

Let $v$ be a $4$-vertex and incident to a $(4,5,5)$-face. If $m_{3}(v)=1$, and
$v$ is incident to at most one $5^{+}$-face, then all neighbours of $v$ are
$5$-vertices.

###### Proof.

Let $v$ be a $4$-vertex with $m_{3}(v)=1$. By Lemma 2.2, we have $n_{3}(v)=0$.
Suppose that $f$ is a $(4,5,5)$-face such that $f=v_{1}vv_{2}$ with
$d(v_{1})=d(v_{2})=5$. Let $v$ be incident to at most one $5^{+}$-face. Assume
for a contradiction that $v$ has a $4$-neighbour, say $v_{3}$. Since
$m_{3}(v)=1$, and $v$ is incident to at most one $5^{+}$-face, we can say that
$v$ is incident to at least two $4$-faces, say $f_{2},f_{3}$. Clearly, we have
$d_{2}(v)\leq 15$. If $f_{2}$ and $f_{3}$ are adjacent, then we set
$G^{\prime}=G-v+\\{v_{2}v_{3},v_{1}v_{4}\\}$. If $f_{2}$ and $f_{3}$ are non-
adjacent, then we set $G^{\prime}=G-v+\\{v_{2}v_{3},v_{3}v_{4}\\}$. In each
case, $G^{\prime}$ is proper with respect to $G$. By minimality, the graph
$G^{\prime}$ has a 2-distance coloring $f$ with $16$ colors. Since
$d_{2}(v)\leq 15$, we can color $v$ with an available color, a contradiction.
Thus, all neighbours of $v$ are $5$-vertices. ∎

We will now present some properties of $5$-vertices, with the assumption that
$v_{1},v_{2},\ldots,v_{5}$ are the neighbours of $v$ in clockwise order.
Furthermore, if $m_{3}(v)=4$, we consider the $3$-faces incident to $v$ as
$f_{1}=v_{1}vv_{2}$, $f_{2}=v_{2}vv_{3}$, $f_{3}=v_{3}vv_{4}$, and
$f_{4}=v_{4}vv_{5}$.

######  Lemma 2.12.

Let $v$ be a $5$-vertex. Then $m_{3}(v)\leq 4$ and $n_{3}(v)\leq 4$.

###### Proof.

Assume to the contrary that all faces incident to $v$ are $3$-faces, i.e,
$m_{3}(v)=5$. Let $G^{\prime}=G-v$. By minimality, the graph $G^{\prime}$ has
a 2-distance coloring $f$ with $16$ colors. Clearly, $G^{\prime}$ is proper
with respect to $G$. Since $v$ has at most $15$ forbidden colors, we can color
$v$ with an available color, a contradiction. Thus, $m_{3}(v)\leq 4$.

Let us now assume that all neighbours of $v$ are $3$-vertices, i.e,
$n_{3}(v)=5$. If we set
$G^{\prime}=G-v+\\{v_{1}v_{2},v_{2}v_{3},v_{3}v_{4},v_{4}v_{5},v_{5}v_{1}\\}$
(if $v_{i}v_{i+1}\notin E(G)$ in mod $5$), then $G^{\prime}$ is proper with
respect to $G$. Similarly as above, we get a contradiction since $d_{2}(v)\leq
15$. Thus, $n_{3}(v)\leq 4$. ∎

######  Proposition 2.13.

Let $v$ be a $5$-vertex. If $m_{3}(v)=n_{3}(v)=2$, then $v$ has at most one
$4$-neighbour.

###### Proof.

Let $m_{3}(v)=n_{3}(v)=2$. Since $n_{3}(v)=2$, the $3$-faces incident to $v$,
say $f_{1}$ and $f_{2}$, must be adjacent by Lemma 2.5. We write
$f_{1}=v_{1}vv_{2}$ and $f_{2}=v_{2}vv_{3}$. By contradiction, assume that $v$
has two $4$-neighbours. This infer that $d_{2}(v)\leq 15$. If we set
$G^{\prime}=G-v+\\{v_{3}v_{4},v_{4}v_{5},v_{5}v_{1}\\}$, then $G^{\prime}$ is
proper with respect to $G$. By minimality, the graph $G^{\prime}$ has a
2-distance coloring $f$ with $16$ colors. Owing to $d_{2}(v)\leq 15$, we can
color $v$ with an available color, a contradiction. ∎

######  Lemma 2.14.

Let $v$ be a $5$-vertex with $n_{3}(v)=1$.

  * $(a)$

If $m_{3}(v)=2$, then $v$ has at most three $4$-neighbours.

  * $(b)$

If $m_{3}(v)=2$, and $v$ has a $4$-neighbour, then $v$ is incident to a
$5^{+}$-face.

  * $(c)$

If $m_{3}(v)=3$, then $v$ has at most one $4$-neighbours and incident to at
least one $5^{+}$-face.

  * $(d)$

If $m_{3}(v)=3$, and $v$ has a $4$-neighbour, then $v$ is incident to two
$5^{+}$-face.

###### Proof.

Let $v_{5}$ be $3$-neighbour of $v$. By Lemma 2.5, $v$ does not belong to any
$3$-face.

(a). Suppose that $m_{3}(v)=2$, and let $f_{1}$ and $f_{2}$ be $3$-faces
incident to $v$. Assume for a contradiction that $v$ has four $4$-neighbours,
and so $v_{1},v_{2},v_{3},v_{4}$ are $4$-vertices. If $f_{1}$ and $f_{2}$ are
adjacent, say $f_{1}=v_{1}vv_{2}$ and $f_{2}=v_{2}vv_{3}$, then we set
$G^{\prime}=G-v+\\{v_{3}v_{4},v_{4}v_{5},v_{1}v_{5}\\}$. If $f_{1}$ and
$f_{2}$ are non-adjacent, say $f_{1}=v_{1}vv_{2}$ and $f_{2}=v_{3}vv_{4}$,
then we set $G^{\prime}=G-v+\\{v_{2}v_{3},v_{4}v_{5},v_{1}v_{5}\\}$. In both
cases, we have $d_{2}(v)\leq 15$ and $G^{\prime}$ is proper with respect to
$G$. By minimality, the graph $G^{\prime}$ has a 2-distance coloring $f$ with
$16$ colors. Since $d_{2}(v)\leq 15$, we can color $v$ with an available
color, a contradiction.

(b). Let $m_{3}(v)=2$ and let $v$ have a $4$-neighbour. By contradiction,
assume that $v$ is not incident to any $5^{+}$-face, i.e., $v$ has three
$4$-faces. Let $f_{1}$ and $f_{2}$ be $3$-faces incident to $v$. If $f_{1}$
and $f_{2}$ are adjacent, say $f_{1}=v_{1}vv_{2}$ and $f_{2}=v_{2}vv_{3}$,
then we set $G^{\prime}=G-v+\\{v_{5}v_{2},v_{5}v_{3},v_{1}v_{4}\\}$, where we
note that $v_{5}$ shares a common neighbor, apart from $v$, with each of
$v_{1}$ and $v_{4}$ since all faces incident to $v$, other than $f_{1}$ and
$f_{2}$, are $4$-faces. If $f_{1}$ and $f_{2}$ are non-adjacent, say
$f_{1}=v_{1}vv_{2}$ and $f_{2}=v_{3}vv_{4}$, then we set
$G^{\prime}=G-v+\\{v_{2}v_{3},v_{4}v_{5},v_{1}v_{5}\\}$. In both cases, we
have $d_{2}(v)\leq 15$ and $G^{\prime}$ is proper with respect to $G$.
Similarly as above, we get a contradiction. Thus, $v$ is incident to a
$5^{+}$-face.

(c). Let $m_{3}(v)=3$ and let $f_{1},f_{2},f_{3}$ be $3$-faces incident to
$v$. We may write $f_{1}=v_{1}vv_{2}$, $f_{2}=v_{2}vv_{3}$, and
$f_{3}=v_{3}vv_{4}$, since $v_{5}$ is not incident to any $3$-face by Lemma
2.5. Assume for a contradiction that $v$ has two $4$-neighbours or all faces
incident to $v$ are $4^{-}$-faces. In both cases, we have $d_{2}(v)\leq 15$.
Let $G^{\prime}=G-v+\\{v_{4}v_{5},v_{5}v_{1}\\}$. Clearly, $G^{\prime}$ is
proper with respect to $G$. Similarly as above, we get a contradiction. Thus,
$n_{4}(v)\leq 1$, and $v$ is incident to at least one $5^{+}$-face.

(d). Let $m_{3}(v)=3$ and let $f_{1},f_{2},f_{3}$ be $3$-faces incident to
$v$. We may write $f_{1}=v_{1}vv_{2}$, $f_{2}=v_{2}vv_{3}$, and
$f_{3}=v_{3}vv_{4}$, since $v_{5}$ is not incident to any $3$-face by Lemma
2.5. Suppose that $v$ has a $4$-neighbour. If $v$ is incident to at most one
$5^{+}$-face, then we would have $d_{2}(v)\leq 15$. In such a case, if we set
$G^{\prime}=G-v+\\{v_{4}v_{5},v_{5}v_{1}\\}$, then $G^{\prime}$ would be
proper with respect to $G$. Similarly as above, we get a contradiction. Thus,
$v$ is incident to two $5^{+}$-faces. ∎

######  Lemma 2.15.

Let $v$ be a $5$-vertex with $n_{3}(v)=0$.

  * $(a)$

If $m_{3}(v)=2$, and all neighbours of $v$ are $4$-vertices, then $v$ is
incident to three $5^{+}$-faces.

  * $(b)$

If $m_{3}(v)=3$, then $v$ has at most three $4$-neighbours.

###### Proof.

(a). Let $m_{3}(v)=2$ and $n_{4}(v)=5$. Assume to the contrary that $v$ is
incident to at most two $5^{+}$-face. This implies that $v$ is incident to a
$4$-face. Clearly, we have $d_{2}(v)\leq 15$. If the $3$-faces incident to $v$
are adjacent, say $f_{1}=v_{1}vv_{2}$, $f_{2}=v_{2}vv_{3}$, then we write
$G^{\prime}=G-v+\\{v_{3}v_{4},v_{4}v_{5},v_{5}v_{1}\\}$. If the $3$-faces
incident to $v$ are not adjacent, say $f_{1}=v_{1}vv_{2}$,
$f_{2}=v_{3}vv_{4}$, then we write
$G^{\prime}=G-v+\\{v_{2}v_{3},v_{4}v_{5},v_{5}v_{1}\\}$. In both cases,
$G^{\prime}$ is proper with respect to $G$. By minimality, the graph
$G^{\prime}$ has a 2-distance coloring $f$ with $16$ colors. Since
$d_{2}(v)\leq 15$, we can color $v$ with an available color, a contradiction.
Thus, $v$ is incident to three $5^{+}$-faces.

(b). Let $m_{3}(v)=3$ and let $f_{1},f_{2},f_{3}$ be $3$-faces incident to
$v$. By contradiction, suppose that $v$ has four $4$-neighbours. Then we have
$d_{2}(v)\leq 15$. If the $3$-faces incident to $v$ are forming
$f_{1}=v_{1}vv_{2}$, $f_{2}=v_{2}vv_{3}$, and $f_{3}=v_{4}vv_{5}$, then we
write $G^{\prime}=G-v+\\{v_{3}v_{4},v_{5}v_{1}\\}$. If the $3$-faces incident
to $v$ are forming $f_{1}=v_{1}vv_{2}$, $f_{2}=v_{2}vv_{3}$, and
$f_{3}=v_{3}vv_{4}$, then we write
$G^{\prime}=G-v+\\{v_{2}v_{5},v_{2}v_{4}\\}$ where we should note that one of
$v_{2}$ or $v_{3}$ must be a $4$-vertex, let’s assume it’s $v_{2}$ by
symmetry. In both cases, $G^{\prime}$ is proper with respect to $G$. Similarly
as above, we get a contradiction. Thus, $n_{4}(v)\leq 3$. ∎

######  Lemma 2.16.

Let $v$ be a $5$-vertex with $n_{3}(v)=0$ and $m_{3}(v)=4$.

  * $(a)$

The vertex $v$ has at most one $4$-neighbour.

  * $(b)$

If $v$ has a $4$-neighbour, $v$ is incident to a $5^{+}$-face.

  * $(c)$

If $v$ is incident to a $4$-face, there is no edge $v_{i}v_{i+1}$ for
$i\in[4]$ contained in two $3$-faces.

  * $(d)$

If $v$ is incident to a $5^{+}$-face, there exists at most one edge
$v_{i}v_{i+1}$ for $i\in[4]$ contained in two $3$-faces.

  * $(e)$

If $v$ is incident to a $5^{+}$-face, and there exists an edge $v_{i}v_{i+1}$
for $i\in[4]$ contained in two $3$-faces, then all neighbour of $v$ are
$5$-vertices.

###### Proof.

Let $f_{1},f_{2},f_{3},f_{4}$ be $3$-faces incident to $v$.

(a). By contradiction, assume that $v$ has two $4$-neighbours, and so
$d_{2}(v)\leq 15$. If we set $G^{\prime}=G-v+\\{v_{5}v_{1}\\}$, then
$G^{\prime}$ is proper with respect to $G$. By minimality, the graph
$G^{\prime}$ has a 2-distance coloring $f$ with $16$ colors. Since $v$ has at
most $15$ forbidden colors, we can color $v$ with an available color, a
contradiction. Thus, $n_{4}(v)\leq 1$.

(b). Suppose that $v$ has a $4$-neighbour and $v$ is incident to a $4$-face.
Then we have $d_{2}(v)\leq 15$. Similarly as above, we get a contradiction.

(c). Suppose that $v$ is incident to a $4$-face. If there is an edge
$v_{i}v_{i+1}$ for $i\in[4]$ contained in two $3$-faces, then we have again
$d_{2}(v)\leq 15$. Similarly as above, we get a contradiction.

(d). Assume that $v$ is incident to a $5^{+}$-face. If there exist two edges
$v_{i}v_{i+1}$ and $v_{j}v_{j+1}$ for $i,j\in[4]$ with $i\neq j$ contained in
two $3$-faces, then we have again $d_{2}(v)\leq 15$. Similarly as above, we
get a contradiction.

(e). Suppose that $v$ is incident to a $5^{+}$-face, and there exists an edge
$v_{i}v_{i+1}$ for $i\in[4]$ contained in two $3$-faces. If $v$ has a
$4$-neighbour, then we have again $d_{2}(v)\leq 15$. Similarly as above, we
get a contradiction. ∎

Let us define some special vertices. Suppose that $v$ is a $5$-vertex, and let
$v_{1},v_{2},\ldots,v_{5}$ be the neighbours of $v$ in clockwise order. If
$m_{3}(v)=4$, and $v$ is incident to a $4$-face (resp. a $5^{+}$-face), we
refer to $v$ as a _bad vertex_ (resp. a _semi-bad vertex_). The other special
vertices are as follows:

We call $v$ as a _strong vertex_ if

  * •

$m_{3}(v)=3$,

  * •

the $3$-faces incident to $v$ are forming $f_{1}=v_{1}vv_{2}$,
$f_{2}=v_{2}vv_{3}$, and $f_{3}=v_{4}vv_{5}$,

  * •

$v_{2}$ is a bad or semi-bad vertex,

  * •

$v$ is incident to a $5^{+}$-face.

We call $v$ as a _good vertex_ if

  * •

$m_{3}(v)=3$,

  * •

the $3$-faces incident to $v$ are forming $f_{1}=v_{1}vv_{2}$,
$f_{2}=v_{2}vv_{3}$, and $f_{3}=v_{3}vv_{4}$,

  * •

$v_{2}$ is a semi-bad vertex,

  * •

each of $v_{1}v_{2}$ and $v_{2}v_{3}$ is contained in two $3$-faces.

We call $v$ as a _support vertex_ if

  * •

$m_{3}(v)=2$,

  * •

$v$ is incident to two adjacent $3$-faces forming $f_{1}=v_{1}vv_{2},$ and
$f_{2}=v_{2}vv_{3}$,

  * •

$v_{2}$ is a bad or semi-bad vertex.

We illustrate these special vertices in Figures 1 and 2 with the assistance of
the results in Remark 2.17 and Lemma 2.19. Notice that all $v_{i}$’s, in
Figure 1(a), are $5$-vertices while $v_{2},v_{3},v_{4}$, in Figure 1(b), are
$5$-vertices by Lemma 2.19(a). Additionally, one of $v_{1}$ or $v_{5}$ in
Figure 1(b) is a $5$-vertex and the other is a $4^{+}$-vertex by Remark
2.17(b).

Moving on to the other special vertices, in Figures 2(a),(b) and (c), the
vertex $v_{2}$ is either a bad or a semi-bad vertex, implying that
$d(v_{2})=5$ and $m_{4}(v_{2})=4$. Furthermore, in Figures 2(a) and 2(c),
$v_{3}$ is a $5$-vertex (resp. $4^{+}$-vertex) if $v_{2}$ is a bad (resp.
semi-bad) vertex by Remark 2.17. In Figure 2(b), all neighbours of $v_{2}$ are
$5$-vertices by Lemma 2.16(e).

$v$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$

$v$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$5^{+}$-face

Figure 1. $(a)$ A bad vertex. $(b)$ A semi-bad vertex.

$v$$v_{3}$$v_{2}$$v_{1}$$v_{4}$$v_{5}$

$v$$v_{3}$$v_{2}$$v_{1}$$5^{+}$-face$v_{4}$$v_{5}$

$v$$v_{3}$$v_{2}$$v_{1}$$v_{4}$$v_{5}$

Figure 2. $(a)$ A strong vertex. $(b)$ A good vertex. $(c)$ A support vertex.

Our next aim is to present the structural properties of the special vertices
defined earlier. Recall that a bad and a semi-bad vertex has $m_{3}(v)=4$.
Therefore, based on this assumption, we can conclude that the $3$-faces
incident to $v$ are $f_{1}=v_{1}vv_{2}$, $f_{2}=v_{2}vv_{3}$,
$f_{3}=v_{3}vv_{4}$, and $f_{3}=v_{4}vv_{5}$. Additionally, a bad or a semi-
bad vertex cannot have any $3$-neighbour by Lemma 2.5.

######  Remark 2.17.

Let $v$ be a $5$-vertex.

  * $(a)$

If $v$ is a bad vertex, then all neighbours of $v$ are $5$-vertices, and no
edge $v_{i}v_{i+1}$ for $i\in[4]$ is contained in two $3$-faces.

  * $(b)$

If $v$ is a semi-bad vertex, then $n_{3}(v)=0$ and $n_{5}(v)\geq 4$.

###### Proof.

(a). Suppose that $v$ is a bad vertex. It follows from Lemma 2.5 that all
$v_{i}$’s are $4^{+}$-vertices. By contradiction, assume that $v$ has a
$4$-neighbour. Since $v,v_{1},v_{5}$ are contained in a $4$-face, we have
$d_{2}(v)\leq 15$. If we set $G^{\prime}=G-v+\\{v_{5}v_{1}\\}$, then
$G^{\prime}$ is proper with respect to $G$. By minimality, the graph
$G^{\prime}$ has a 2-distance coloring $f$ with $16$ colors. Since $v$ has at
most $15$ forbidden colors, we can color $v$ with an available color, a
contradiction. Thus, $n_{5}(v)=5$. If an edge $v_{i}v_{i+1}$ for $i\in[4]$ is
contained in two $3$-faces, then we would have again $d_{2}(v)\leq 15$.
Similarly as above, we get a contradiction.

(b). Suppose that $v$ is a semi-bad vertex. If $v$ has a $3$-neighbour or two
$4$-neighbours, then we would have $d_{2}(v)\leq 15$. When we set
$G^{\prime}=G-v+\\{v_{5}v_{1}\\}$, $G^{\prime}$ would be proper with respect
to $G$. Similarly as above, we get a contradiction. ∎

######  Remark 2.18.

A bad vertex cannot have any bad or semi-bad neighbour.

###### Proof.

Let $v$ be a bad vertex. Since there is no edge $v_{i}v_{i+1}$ for $i\in[4]$
contained in two $3$-faces by Lemma 2.16(c), none of $v_{i}$’s can be incident
to four $3$-faces, i.e., we have $m_{3}(v_{i})\leq 3$ for each $v_{i}\in
N(v)$. This implies that no neighbour of $v$ is a bad or a semi-bad vertex.
So, the claim holds. ∎

######  Lemma 2.19.

Let $v$ be a bad or a semi-bad vertex (see Figure 1). Then the followings
hold.

  * $(a)$

$v_{2},v_{3},v_{4}$ are $5$-vertices.

  * $(b)$

If $v$ is a bad vertex, $v_{3}$ is either a support or a strong vertex.

  * $(c)$

If $v$ is a semi-bad vertex, then $v_{3}$ is either a support or a strong or a
good vertex.

###### Proof.

(a). Assume for a contradiction that there exists
$v_{i}\in\\{v_{2},v_{3},v_{4}\\}$ such that it is a $4$-vertex, without loss
of generality, say $v_{i}=v_{2}$ and let $x\in
N(v_{2})\setminus\\{v,v_{1},v_{3}\\}$. We observe that $d_{2}(v_{2})\leq 15$.
If we set $G^{\prime}=G-v+\\{v_{1}x,xv_{3}\\}$, then $G^{\prime}$ is proper
with respect to $G$. By minimality, the graph $G^{\prime}$ has a 2-distance
coloring with $16$ colors. Since $d_{2}(v_{2})\leq 15$, we can color $v$ with
an available color, a contradiction. Thus, $v_{2},v_{3},v_{4}$ are
$5$-vertices.

(b). Let $v$ be a bad vertex. By (a), $v_{3}$ is a $5$-vertex, and so we
denote by $v_{4},v,v_{2},x,y$ the neighbours of $v_{3}$ in clockwise order. If
$m_{3}(v_{3})=2$, then $v_{3}$ would be a support vertex. Notice that the case
$m_{3}(v_{3})=4$ is not possible by Remark 2.18. Thus, we may suppose that
$m_{3}(v_{3})=3$, and so $xy\in E(G)$ by Lemma 2.16(c). If all faces incident
to $v_{3}$ are $4^{-}$-faces, then we have $d_{2}(v_{3})\leq 15$ since $v$ has
two common neighbours with each of $v_{2},v_{4}$. In such a case, we set
$G^{\prime}=G-v+\\{v_{2}x,yv_{4}\\}$. Similarly as above, we get a
contradiction. We therefore conclude that $v_{3}$ is incident to a
$5^{+}$-face, and so $v_{3}$ becomes a strong vertex.

(c). Let $v$ be a semi-bad vertex. The vertex $v_{3}$ is a $5$-vertex by (a),
and denote by $v_{4},v,v_{2},x,y$ the neighbours of $v_{3}$ in clockwise
order. If $m_{3}(v_{3})=2$, then $v_{3}$ is a support vertex by its
definition. So, we may suppose that $m_{3}(v_{3})\geq 3$. We remark that if
$m_{3}(v_{3})=4$, then $v_{3}$ becomes a bad or a semi-bad vertex, however,
both $v_{2}v$ and $vv_{4}$ would be contained in two $3$-faces, which
contradicts Lemma 2.16(c)-(d). Therefore we may assume that $m_{3}(v_{3})=3$.
If none of the edges $v_{2}v_{3},v_{3}v_{4}$ is contained in two $3$-faces,
then similarly as above, we conclude that $v_{3}$ is incident to a
$5^{+}$-face, and so $v_{3}$ is a strong vertex. If only one of the edges
$v_{2}v_{3},v_{3}v_{4}$ is contained in two $3$-faces, by symmetry, we may
assume it is $v_{2}v_{3}$, then $v_{3}$ becomes a good vertex. ∎

######  Lemma 2.20.

Let $v$ be a strong vertex with $3$-faces $f_{1}=v_{1}vv_{2}$,
$f_{2}=v_{2}vv_{3}$ and $f_{3}=v_{4}vv_{5}$.

  * $(a)$

If $v$ has two $4$-neighbours, then $v$ is incident to two $5^{+}$-face.

  * $(b)$

If $v_{2}$ has two common neighbours with each of $v_{1},v_{3}$, then either
$v$ has no $4$-neighbour or $v$ is incident to two $5^{+}$-face.

###### Proof.

(a). Let $v$ be a strong vertex with $3$-faces $f_{1}=v_{1}vv_{2}$,
$f_{2}=v_{2}vv_{3}$ and $f_{3}=v_{4}vv_{5}$. Then $v_{2}$ is a bad or semi-bad
vertex, this implies that at least one of $v_{1}v_{2}$ and $v_{2}v_{3}$ is
contained in two $3$-faces. Suppose that $v$ has two $4$-neighbours. By
contradiction, assume that $v$ is incident to at most one $5^{+}$-face. Thus,
we have $d_{2}(v)\leq 15$. If we set
$G^{\prime}=G-v+\\{v_{3}v_{4},v_{1}v_{5}\\}$, then $G^{\prime}$ would be
proper with respect to $G$. By minimality, the graph $G^{\prime}$ has a
2-distance coloring with $16$ colors. Since $v$ has at most $15$ forbidden
colors, we can color $v$ with an available color, a contradiction. Hence, $v$
is incident to two $5^{+}$-faces.

(b). Suppose that $v_{2}$ has two common neighbours with each of
$v_{1},v_{3}$. By contradiction, assume that $v$ has a $4$-neighbour and $v$
is incident to a $4$-face. Clearly, we have $d_{2}(v)\leq 15$. Similarly as
above, we get a contradiction. So the claim holds. ∎

######  Proposition 2.21.

Let $v$ be a good vertex with $3$-faces $f_{1}=v_{1}vv_{2}$,
$f_{2}=v_{2}vv_{3}$, and $f_{3}=v_{3}vv_{4}$. If $n_{4}(v)=1$, and $v$ is
incident to exactly two $5^{+}$-faces, then only one of $v_{2},v_{3}$ can be
semi-bad vertex.

###### Proof.

Suppose that $n_{4}(v)=1$, and $v$ is incident to exactly two $5^{+}$-faces.
It follows from the definition of good vertex, each of $v_{1}v_{2}$,
$v_{2}v_{3}$ is contained in two $3$-faces. By contradiction, assume that both
$v_{2}$ and $v_{3}$ are semi-bad vertices. It then follows from Lemma 2.16(d)
that $v_{3}v_{4}$ is contained in two $3$-faces. This implies that
$d_{2}(v)\leq 15$. By Lemma 2.19(a), the vertices $v_{1},v_{2},v_{3},v_{4}$
are $5$-vertices. We then deduce that $v_{5}$ is a $4$-vertex since
$n_{4}(v)=1$. Thus, if we set $G^{\prime}=G-v+\\{v_{1}v_{5},v_{4}v_{5}\\}$,
then $G^{\prime}$ would be proper with respect to $G$. By minimality, the
graph $G^{\prime}$ has a 2-distance coloring with $16$ colors. Since $v$ has
at most $15$ forbidden colors, we can color $v$ with an available color, a
contradiction. ∎

######  Lemma 2.22.

Let $v$ be a good vertex with $3$-faces $f_{1}=v_{1}vv_{2}$,
$f_{2}=v_{2}vv_{3}$ and $f_{3}=v_{3}vv_{4}$ such that $v_{2}$ is a semi-bad
vertex. The followings hold.

  * $(a)$

$v$ has no $3$-neighbour.

  * $(b)$

$v$ has at most one $4$-neighbour.

  * $(c)$

$v$ is incident to a $5^{+}$-face.

  * $(d)$

If $v$ has a $4$-neighbour, then $v$ is incident to two $5^{+}$-face.

  * $(e)$

If $v_{3}$ is also a semi-bad vertex, then $v$ is incident to two
$5^{+}$-face.

###### Proof.

By the definition of good vertex, each of $v_{1}v_{2}$, $v_{2}v_{3}$ is
contained in two $3$-faces. Denote by $f_{1},f_{2},\ldots,f_{5}$ the faces
incident to $v$.

(a). By contradiction, assume that $v$ has a $3$-neighbour, which should be
$v_{5}$ by Lemma 2.5. Clearly, we have $d_{2}(v)\leq 15$. If we set
$G^{\prime}=G-v+\\{v_{4}v_{5},v_{5}v_{1}\\}$, then $G^{\prime}$ is proper with
respect to $G$. By minimality, the graph $G^{\prime}$ has a 2-distance
coloring with $16$ colors. Since $d_{2}(v)\leq 15$, we can color $v$ with an
available color, a contradiction. Thus, $v$ has no $3$-neighbour.

(b). Assume to the contrary that $v$ has two $4$-neighbours. Thus we have
$d_{2}(v)\leq 15$. Notice that $v_{1},v_{2},v_{3}$ are $5$-vertices by Lemma
2.19(a). It then follows that $v_{4}$ and $v_{5}$ are $4$-vertices by the
assumption. If we set $G^{\prime}=G-v+\\{v_{1}v_{5},v_{4}v_{5}\\}$, then
$G^{\prime}$ is proper with respect to $G$. Similarly as above, we get a
contradiction. So, $v$ has at most one $4$-neighbour.

(c). Suppose that $v$ is incident to no $5^{+}$-face, i.e., $f_{4},f_{5}$ are
$4$-faces. This means that $v_{5}$ has a common neighbour, except for $v$,
with each of $v_{1},v_{4}$. Clearly, we have $d_{2}(v)\leq 15$. If we set
$G^{\prime}=G-v+\\{v_{1}v_{4},v_{3}v_{5}\\}$, then $G^{\prime}$ would be
proper with respect to $G$. Similarly as above, we get a contradiction. Thus,
$v$ is incident to a $5^{+}$-face.

(d). Suppose that $v$ has a $4$-neighbour, and assume for a contradiction that
$v$ is incident to at most one $5^{+}$-face. This implies that at least one of
$f_{4},f_{5}$ is a $4$-face. Without loss of generality, assume that $f_{4}$
is a $4$-face forming $f_{4}=vv_{4}xv_{5}$. Clearly, we have $d_{2}(v)\leq
15$. If we set $G^{\prime}=G-v+\\{v_{1}v_{4},v_{2}v_{5}\\}$, then $G^{\prime}$
would be proper with respect to $G$. Similarly as above, we get a
contradiction. Hence, $v$ is incident to two $5^{+}$-faces.

(e) Suppose that $v_{3}$ is also a semi-bad vertex. Since $v_{2}$ is a semi-
bad vertex, $v_{3}v_{4}$ is contained in two $3$-faces by Lemma 2.16(d).
Consequently, each of $v_{1}v_{2}$, $v_{2}v_{3}$, $v_{3}v_{4}$ is contained in
two $3$-faces. If $v$ is incident to at most one $5^{+}$-face, then at least
one of $f_{4},f_{5}$ is a $4$-face. Without loss of generality, assume that
$f_{4}$ is a $4$-face forming $f_{4}=vv_{4}xv_{5}$. Clearly, we have
$d_{2}(v)\leq 15$ since each of $v_{1}v_{2}$, $v_{2}v_{3}$, $v_{3}v_{4}$ is
contained in two $3$-faces. If we set
$G^{\prime}=G-v+\\{v_{1}v_{4},v_{2}v_{5}\\}$, then $G^{\prime}$ would be
proper with respect to $G$. Similarly as above, we get a contradiction. ∎

######  Lemma 2.23.

Let $v$ be a support vertex.

  * $(a)$

If $n_{3}(v)=1$, then $v$ is incident to a $5^{+}$-faces.

  * $(b)$

If $n_{3}(v)=1$ and $n_{4}(v)=1$, then $v$ is incident to two $5^{+}$-faces.

  * $(c)$

If $n_{3}(v)=1$ and $n_{4}(v)=2$, then $v$ is incident to three $5^{+}$-faces.

  * $(d)$

If $n_{3}(v)=2$, then $v$ is incident to three $5^{+}$-faces.

###### Proof.

Let $v$ be a support vertex with $3$-faces $f_{1}=v_{1}vv_{2}$ and
$f_{2}=v_{2}vv_{3}$. Then $v_{2}$ is a bad or semi-bad vertex, this implies
that at least one of $v_{1}v_{2}$ and $v_{2}v_{3}$ is contained in two
$3$-faces.

(a). Let $n_{3}(v)=1$. Assume to the contrary that all faces incident to $v$
other than $f_{1},f_{2}$ are $4$-faces. We then say that each pair of
$\\{v_{3},v_{4}\\},\\{v_{4},v_{5}\\},\\{v_{1},v_{5}\\}$ has a common neighbour
in $G-v$. Clearly, we have $d_{2}(v)\leq 15$. Thus, if we set
$G^{\prime}=G-v+\\{v_{3}v_{5},v_{2}v_{4}\\}$, then $G^{\prime}$ would be
proper with respect to $G$. By minimality, the graph $G^{\prime}$ has a
2-distance coloring $f$ with $16$ colors. Since $v$ has at most $15$ forbidden
colors, we can color $v$ with an available color, a contradiction. Hence, $v$
is incident to a $5^{+}$-face.

(b). Let $n_{3}(v)=1$ and $n_{4}(v)=1$. By Lemma 2.5, the $3$-neighbour of $v$
is either $v_{4}$ or $v_{5}$. Assume, without loss of generality, that $v_{5}$
is a $3$-vertex. Denote by $f_{1},f_{2},\ldots,f_{5}$ the faces incident to
$v$ in clockwise order on the plane. By (a), $v$ is incident to a
$5^{+}$-face. Assume to the contrary that $v$ is incident to two $4$-faces,
i.e., two of $f_{3},f_{4},f_{5}$ are $4$-face. We then have $d_{2}(v)\leq 15$.
As $v$ is incident to two $4$-faces and one $5^{+}$-face, we consider all
possible cases. If $f_{3}$ is a $5^{+}$-face, then we set
$G^{\prime}=G-v+\\{v_{2}v_{4},v_{3}v_{5},v_{1}v_{5}\\}$. If $f_{4}$ or $f_{5}$
is a $5$-face, then we set
$G^{\prime}=G-v+\\{v_{1}v_{5},v_{2}v_{5},v_{4}v_{5}\\}$. In both cases, we can
say that $G^{\prime}$ is proper with respect to $G$. Similarly as above, we
get a contradiction. Hence, $v$ is incident to two $5^{+}$-faces.

(c). Let $n_{3}(v)=1$ and $n_{4}(v)=2$. By Lemma 2.5, the $3$-neighbour of $v$
is either $v_{4}$ or $v_{5}$. We may suppose that $v_{5}$ is a $3$-vertex.
Assume to the contrary that $v$ is incident to at most two $5^{+}$-faces. This
implies that $v$ is incident to a $4$-face. Since at most one of $v_{1},v_{3}$
is a $4$-vertex by Remark 2.17(b), we may assume that $v_{3},v_{4}$ are
$4$-vertices due to $n_{4}(v)=2$ and $n_{3}(v)=1$. In such a case, we have
$d_{2}(v)\leq 15$ and so we set
$G^{\prime}=G-v+\\{v_{3}v_{4},v_{4}v_{5},v_{5}v_{1}\\}$. Clearly, $G^{\prime}$
is proper with respect to $G$. Similarly as above, we get a contradiction.

(d). Let $n_{3}(v)=2$. So, $v_{4},v_{5}$ are $3$-vertices by Lemma 2.5.
Suppose that $v$ is incident to a $4$-face. In such a case, we have
$d_{2}(v)\leq 15$ and so we set
$G^{\prime}=G-v+\\{v_{3}v_{4},v_{4}v_{5},v_{5}v_{1}\\}$. Clearly, $G^{\prime}$
is proper with respect to $G$. Similarly as above, we get a contradiction. ∎

In the rest of the paper, we will apply discharging to show that $G$ does not
exist. We assign to each vertex $v$ a charge $\mu(v)=d(v)-4$ and to each face
$f$ a charge $\mu(f)=\ell(f)-4$. By Euler’s formula, we have

$\sum_{v\in V}\left(d(v)-4\right)+\sum_{f\in F}(\ell(f)-4)=-8$

We next present some rules and redistribute accordingly. Once the discharging
finishes, we check the final charge $\mu^{*}(v)$ and $\mu^{*}(f)$. If
$\mu^{*}(v)\geq 0$ and $\mu^{*}(f)\geq 0$, we get a contradiction that no such
a counterexample can exist.

###  2.2. Discharging Rules

We apply the following discharging rules.

  * R1:

Every $3$-face receives $\frac{1}{3}$ from each of its incident vertex.

  * R2:

Every $3$-vertex receives $\frac{1}{9}$ from each of its $5$-neighbour.

  * R3:

Every $3$-vertex receives $\frac{1}{3}$ from each of its incident
$5^{+}$-face.

  * R4:

Every $4$-vertex receives $\frac{1}{5}$ from each of its incident
$5^{+}$-face.

  * R5:

Every $5$-vertex receives $\frac{1}{5}$ from each of its incident $5^{+}$-face
$f$ if $f$ does not contain any $3$-neighbour of $v$.

  * R6:

Every $5$-vertex receives $\frac{1}{9}$ from each of its incident $5^{+}$-face
$f$ if $f$ contains a $3$-neighbour of $v$.

  * R7:

Let $v$ be a $5$-vertex with $m_{3}(v)\leq 3$, and let $u$ be a $4$-neighbour
of $v$.

    * (a)

If $uv$ belongs to only one $5^{+}$-face, then $v$ gives $\frac{1}{15}$ to
$u$.

    * (b)

If $uv$ belongs to two $5^{+}$-faces, then $v$ gives $\frac{2}{15}$ to $u$.

  * R8:

Let $v$ be a strong vertex with $3$-faces $f_{1}=v_{1}vv_{2}$,
$f_{2}=v_{2}vv_{3}$, and $f_{3}=v_{4}vv_{5}$. Suppose that $v_{2}$ is a bad or
a semi-bad vertex.

    * (a)

If exactly one of $v_{1}v_{2},v_{2}v_{3}$ is contained in two $3$-faces, then
$v$ gives $\frac{2}{15}$ to $v_{2}$.

    * (b)

If both $v_{1}v_{2}$ and $v_{2}v_{3}$ are contained in two $3$-faces, then $v$
gives $\frac{1}{5}$ to $v_{2}$.

  * R9:

Let $v$ be a good vertex with $3$-faces $f_{1}=v_{1}vv_{2}$,
$f_{2}=v_{2}vv_{3}$, and $f_{3}=v_{3}vv_{4}$. If $v_{2}$ (or $v_{3}$) is a
semi-bad vertex, then it receives $\frac{1}{5}$ from $v$.

  * R10:

Every support vertex $v$ gives $\frac{1}{3}$ to its each bad and semi-bad
neighbour $u$ if $vu$ is contained in two $3$-faces.

Checking $\mu^{*}(v),\mu^{*}(f)\geq 0$, for $v\in V(G),f\in F(G)$

First we show that $\mu^{*}(f)\geq 0$ for each $f\in F(G)$. Given a face $f\in
F(G)$. If $f$ is a $3$-face, then it receives $\frac{1}{3}$ from each of
incident vertex by R1. If $f$ is a $4$-face, then $\mu(f)=\mu^{*}(f)=0$. Let
$f$ be a $5$-face. Notice that $f$ is not incident to more than two
$3$-vertices by Corollary 2.3(a). If $f$ is incident to two $3$-vertices,
which are clearly non-adjacent by Lemma 2.2, then all the other vertices
incident to $f$ are $5$-vertices by Corollary 2.3(b), and so each of them
receives $\frac{1}{9}$ from $f$ by R6. Also, $f$ sends $\frac{1}{3}$ to both
$3$-vertices incident to $f$ by R3. Thus, $\mu^{*}(f)=0$. If $f$ is incident
to exactly one $3$-vertex, then $f$ is incident to at most two $4$-vertices by
Corollary 2.3(c). Thus two $5$-vertices incident to $f$ receives $\frac{1}{9}$
from $f$ by R6, and the other $4^{+}$-vertices receive at most $\frac{1}{5}$
from $f$ by R4-R5. Thus $\mu^{*}(f)=0$ after $f$ sends $\frac{1}{3}$ to its
incident $3$-vertex by R3. Finally, if $f$ is not incident to any $3$-vertex,
then $\mu^{*}(f)\geq 0$ after $f$ sends at most $\frac{1}{5}$ to its each
incident vertex by R4-R5.

If $f$ is a $6^{+}$-face, then $\mu(f)=\ell(f)-4\geq 2$, similarly as above,
we have $\mu^{*}(f)\geq 0$ by Corollary 2.4. Consequently, we have
$\mu^{*}(f)\geq 0$ for each $f\in F(G)$.

We now pick a vertex $v\in V(G)$ with $d(v)=k$. By Lemma 2.1, we have $k\geq
3$.

(1). Let $k=3$. By Lemma 2.5, $v$ is not incident to any $3$-face. Also, all
neighbours of $v$ are $5$-vertices by Lemma 2.2. So, $v$ receives
$\frac{1}{9}$ from its each neighbour by R2. On the other hand, $v$ is
incident to at least two $5^{+}$-faces by Lemma 2.5. It follows from applying
R3 that $v$ receives $\frac{1}{3}$ from its each incident $5^{+}$-face, and so
$\mu^{*}(v)\geq d(v)-4+3\times\frac{1}{9}+2\times\frac{1}{3}=0$.

(2). Let $k=4$. Denote by $v_{1},v_{2},v_{3},v_{4}$ the neighbours of $v$.
Recall that all $v_{i}$’s are $4^{+}$-vertices by Lemma 2.2. Obviously
$\mu^{*}(v)\geq 0$ when $m_{3}(v)=0$ since $v$ does not have to give a charge
to any vertex. We may therefore assume that $m_{3}(v)\geq 1$. In addition, we
have $m_{3}(v)\leq 2$ by Lemma 2.6.

First suppose that $m_{3}(v)=1$. Let $f=v_{1}vv_{2}$ be the $3$-face incident
to $v$. Observe that if $v$ is incident to at least two $5^{+}$-faces, then
$v$ receives $\frac{1}{5}$ from its each incident $5^{+}$-face by R4, and so
$\mu^{*}(v)\geq 0$ after $v$ sends $\frac{1}{3}$ to $f$ by R1. Thus we may
further assume that $v$ is incident to at most one $5^{+}$-face. If $f$ is a
$(4,4,4^{+})$-face, then, by Lemma 2.9, $v$ is incident to two $5^{+}$-faces,
it is a contradiction with the assumption. Suppose now that $f$ is a
$(4,5,5)$-face. Notice that both $v_{3}$ and $v_{4}$ are $5$-vertices by
Proposition 2.11. It then follows from Lemma 2.10 that $v$ is incident to
exactly one $5^{+}$-face, say $f^{\prime}$. This implies that $m_{4}(v)=2$.
Suppose first that $f$ and $f^{\prime}$ are adjacent, then $v_{1}v_{2}$ is not
contained in two $3$-faces by Proposition 2.7. Thus, for every $i\in[4]$, we
conclude that $m_{3}(v_{i})\leq 3$. Since $f$ and $f^{\prime}$ are adjacent,
we may assume, without loss of generality, that $f^{\prime}$ contains the path
$v_{2}vv_{3}$. Therefore, $v$ receives at least $\frac{1}{15}$ from each
$v_{2}$ and $v_{3}$ by R7(a), and $\frac{1}{5}$ from $f^{\prime}$ by R4. Thus,
$v$ receives totally at least $\frac{2}{15}+\frac{1}{5}$ from its
$5$-neighbours, and its incident $5^{+}$-face. Consequently $\mu^{*}(v)\geq 0$
after $v$ sends $\frac{1}{3}$ to $f$ by R1. Suppose next that $f$ and
$f^{\prime}$ are non-adjacent. It turns out that $f^{\prime}$ is a
$5^{+}$-face containing the path $v_{3}vv_{4}$. Observe that both $v_{3}$ and
$v_{4}$ are incident to at least two $4^{+}$-faces, so we have
$m_{3}(v_{3})\leq 3$ and $m_{3}(v_{4})\leq 3$. It then follows that $v$
receives at least $\frac{1}{15}$ from each $v_{3}$ and $v_{4}$ by R7(a), and
$\frac{1}{5}$ from $f^{\prime}$ by R4. Thus, $v$ receives totally at least
$\frac{1}{3}$ from its $5$-neighbours, and its incident $5^{+}$-face.
Consequently $\mu^{*}(v)\geq 0$ after $v$ sends $\frac{1}{3}$ to $f$ by R1.

We now suppose that $m_{3}(v)=2$. Let $f_{1},f_{2}$ be $3$-faces incident to
$v$. By Lemma 2.6, all neighbours of $v$ are $5$-vertices, and $v$ is incident
to two $5^{+}$-faces, say $f_{3},f_{4}$. Moreover, no edge in $G[N(v)]$ is
contained in two $3$-faces by Proposition 2.8. Thus, for every $i\in[4]$, we
have $m_{3}(v_{i})\leq 3$. By applying R4, $v$ receives $\frac{1}{5}$ from its
each incident $5^{+}$-face. If $f_{1}$ and $f_{2}$ are non-adjacent, then $v$
receives $\frac{1}{15}$ from its each neighbour by R7(a). If $f_{1}$ and
$f_{2}$ are adjacent, then there exists $u\in N(v)$ such that $uv$ belongs to
two $5^{+}$-faces. So, $v$ receives $\frac{2}{15}$ from $u$ by R7(b), and
$\frac{1}{15}$ from its every other neighbours R7(a). Thus, $v$ receives
totally at least $\frac{2}{3}$ from its $5$-neighbours, and its incident
$5$-faces. Consequently $\mu^{*}(v)\geq 0$ after $v$ sends $\frac{1}{3}$ to
each $f_{1}$ and $f_{2}$ by R1.

(3). Let $k=5$. Denote by $v_{1},\ldots,v_{5}$ the neighbours of $v$ in
clockwise order, and let $f_{1},f_{2},\ldots,f_{5}$ be faces incident to $v$.
By Lemma 2.12, $n_{3}(v)\leq 4$ and $m_{3}(v)\leq 4$. We first note that if
$v$ is incident to at most one $3$-face, then $\mu^{*}(v)\geq 0$ after $v$
sends $\frac{1}{9}$ to its each $3$-neighbour by R2, $\frac{1}{3}$ to its
incident $3$-face by R1 (if exists), and at most $\frac{2}{15}$ to its each
$4$-neighbour by R7. We may therefore assume that $m_{3}(v)\geq 2$. Observe
that if $v$ is adjacent to at least three $3$-vertices, then at most one of
$f_{i}$’s can be $3$-face, a contradiction with the assumption. Thus we also
assume that $n_{3}(v)\leq 2$.

(3.1). Let $n_{3}(v)=2$. Then at most two of $f_{i}$’s can be $3$-face by
Lemma 2.5. Indeed, by the assumption of $m_{3}(v)\geq 2$, we say that exactly
two of $f_{i}$’s are $3$-faces. Let $f_{1},f_{2}$ be those $3$-faces. It
follows from Lemma 2.5 that $f_{1}$ and $f_{2}$ are adjacent since
$n_{3}(v)=2$, say $f_{1}=v_{1}vv_{2}$, $f_{2}=v_{2}vv_{3}$. Clearly, $v_{4}$
and $v_{5}$ are $3$-vertices. If $v$ is a support vertex, then $v_{2}$ is a
bad or semi-bad vertex. In such a case, $v$ is incident to three $5^{+}$-faces
by Lemma 2.23(d), and at most one of $v_{1},v_{3}$ is a $4$-vertex by
Proposition 2.13. By R6, $v$ receives $\frac{1}{9}$ from its each incident
$5^{+}$-face. Thus $\mu^{*}(v)\geq 0$ after $v$ sends $\frac{1}{3}$ to its
each incident $3$-face by R1, at most $\frac{1}{3}$ to $v_{2}$ by R10,
$\frac{1}{9}$ to its each $3$-neighbour by R2 and $\frac{1}{15}$ to its
$4$-neighbour by R7(a) (if exists).

Let us now assume that $v$ is not a support vertex. Since at most one of
$v_{i}$’s is a $4$-vertex by Proposition 2.13, we have $\mu^{*}(v)\geq 0$
after $v$ sends $\frac{1}{3}$ to its each incident $3$-face by R1,
$\frac{1}{9}$ to its each $3$-neighbour by R2, and $\frac{1}{15}$ to its
$4$-neighbour by R7(a) (if exists).

(3.2). Let $n_{3}(v)=1$. Clearly, we have $2\leq m_{3}(v)\leq 3$ by Lemma 2.5.
Denote by $v_{5}$ the $3$-neighbour of $v$.

(3.2.1). Let $m_{3}(v)=2$. By Lemma 2.14(a), $v$ has at most three
$4$-neighbours, i.e., $n_{4}(v)\leq 3$. Notice that $v$ is incident to a
$5^{+}$-face when $v$ has a $4$-neighbour by Lemma 2.14(b). In such a case,
$v$ receives at least $\frac{1}{9}$ from its incident $5^{+}$-face by R5-R6.

Let us first assume that $f_{1}$ and $f_{2}$ are non-adjacent, say
$f_{1}=v_{1}vv_{2}$ and $f_{2}=v_{3}vv_{4}$. Then, we note that no $vv_{i}$ is
contained in two $5^{+}$-face for $i\in[5]$, since $d(v_{5})=3$. This means
that the rule R7(b) cannot be applied for $v$. Thus, $\mu^{*}(v)\geq 0$ after
$v$ sends $\frac{1}{3}$ to its each incident $3$-face by R1, $\frac{1}{9}$ to
its $3$-neighbour by R2, and $\frac{1}{15}$ to its each $4$-neighbour by
R7(a).

Assume further that $f_{1}$ and $f_{2}$ are adjacent, say $f_{1}=v_{1}vv_{2},$
and $f_{2}=v_{2}vv_{3}$. Denote by $f_{1},f_{2},\ldots,f_{5}$ the faces
incident to $v$ in clockwise order on the plane. Notice that if there exists a
$4$-vertex $v_{i}\in N(v)$ such that $vv_{i}$ is contained in two
$5^{+}$-faces, then $v$ receives totally at least $\frac{1}{9}+\frac{1}{5}$
from its incident $5^{+}$-faces by R5-R6, since $v_{5}$ is a $3$-vertex. In
fact, only $vv_{4}$ among all $vv_{i}$’s can belong to two $5^{+}$-faces. So,
$v$ sends totally at most $2\times\frac{1}{15}+\frac{2}{15}$ to its all
$4$-neighbours by R7 because of $d(v_{5})=3$ and $n_{4}(v)\leq 3$. Notice that
$v$ may be a support vertex or not, so we will consider these two cases
separately as follows.

Suppose that $v$ is not a support vertex. So $v_{2}$ does not receive any
charge from $v$, even if it is $4$-vertex, according to R7. If $v$ has no
$4$-neighbour, then $\mu^{*}(v)\geq 0$ after $v$ sends $\frac{1}{3}$ to its
each incident $3$-face by R1, $\frac{1}{9}$ to its $3$-neighbour by R2. If $v$
has a $4$-neighbour, then $v$ receives at least $\frac{1}{9}$ from its
incident $5^{+}$-face by R5-R6, which exists by Lemma 2.14(b), and so
$\mu^{*}(v)\geq 0$ after $v$ sends $\frac{1}{3}$ to its each incident $3$-face
by R1, $\frac{1}{9}$ to its $3$-neighbour by R2, $\frac{1}{15}$ to each
$v_{1},v_{3}$ by R7(a) when they are $4$-vertices, at most $\frac{2}{15}$ to
$v_{4}$ by R7(a)-(b) when it is a $4$-vertex.

Suppose now that $v$ is a support vertex. Then $v_{2}$ is a bad or semi-bad
vertex, and so $v_{2}$ has two common neighbours with at least one of
$v_{1},v_{3}$. By Remark 2.17(a)-(b), $v_{2}$ has at most one $4$-neighbour,
and by this way, $v$ has at most two $4$-neighbours. In particular, $v$ is
incident to a $5^{+}$-face by Lemma 2.23(a). We distinguish the rest of the
proof according to the number of $4$-neighbours of $v$.

Let $n_{4}(v)=0$. Then $v$ receives at least $\frac{1}{9}$ from its incident
$5^{+}$-face by R5-R6, and so we have $\mu^{*}(v)\geq 0$ after $v$ sends
$\frac{1}{3}$ to its each incident $3$-face by R1, $\frac{1}{3}$ to $v_{2}$ by
R10, $\frac{1}{9}$ to its $3$-neighbour by R2.

Let $n_{4}(v)=1$. Then $v$ is incident to two $5^{+}$-faces by Lemma 2.23(b).
If $f_{3}$ and $f_{4}$ are $5^{+}$-face, then $v$ receives $\frac{1}{9}$ from
$f_{4}$ by R6, and $\frac{1}{5}$ from $f_{3}$ by R5. Thus we have
$\mu^{*}(v)\geq 0$ after $v$ sends $\frac{1}{3}$ to its each incident $3$-face
by R1, $\frac{1}{3}$ to $v_{2}$ by R10, $\frac{1}{9}$ to its $3$-neighbour by
R2, at most $\frac{2}{15}$ to its $4$-neighbour by R7. If one of $f_{3},f_{4}$
is not a $5^{+}$-face, then $v$ receives at least $\frac{1}{9}$ from its each
incident $5^{+}$-face by R5-R6. Thus we have $\mu^{*}(v)\geq 0$ after $v$
sends $\frac{1}{3}$ to its each incident $3$-face by R1, $\frac{1}{3}$ to
$v_{2}$ by R10, $\frac{1}{9}$ to its $3$-neighbour by R2, $\frac{1}{15}$ to
its $4$-neighbour by R7(a).

Let $n_{4}(v)=2$. Denote by $v_{3},v_{4}$ (or $v_{1},v_{4}$) the
$4$-neighbours of $v$, then $v$ is incident to three $5^{+}$-faces by Lemma
2.23(c). In this case, by R5-R6, $v$ receives at least $\frac{1}{9}$ from its
each incident $5^{+}$-face. Therefore we have $\mu^{*}(v)\geq 0$ after $v$
sends $\frac{1}{3}$ to its each incident $3$-face by R1, $\frac{1}{3}$ to
$v_{2}$ by R10, $\frac{1}{9}$ to its $3$-neighbour by R2, $\frac{1}{15}$ to
$v_{3}$ by R7(a), and $\frac{2}{15}$ to $v_{4}$ by R7(b).

(3.2.2). Let $m_{3}(v)=3$. Denote by $f_{1},f_{2},\ldots,f_{5}$ the faces
incident to $v$ in clockwise order on the plane. By Lemma 2.5 together with
the fact $d(v_{5})=3$, we say that the $3$-faces incident to $v$ are forming
$f_{1}=v_{1}vv_{2}$, $f_{2}=v_{2}vv_{3}$, and $f_{3}=v_{3}vv_{4}$. Notice that
$v$ cannot be a good vertex by Lemma 2.22(a), since $v$ has the $3$-neighbour
$v_{5}$. By Lemma 2.14(c), $v$ has at most one $4$-neighbour, and at least one
of $f_{4},f_{5}$ is a $5^{+}$-face. Suppose first that $v$ has no
$4$-neighbour. By R6, $v$ receives $\frac{1}{9}$ from its each incident
$5^{+}$-face. Thus, $\mu^{*}(v)\geq 0$ after $v$ sends $\frac{1}{3}$ to its
each incident $3$-face by R1 and $\frac{1}{9}$ to its $3$-neighbour by R2.
Suppose now that $v$ has exactly one $4$-neighbour. In this case, $v$ is
incident to two $5^{+}$-faces by Lemma 2.14(d), so $f_{4},f_{5}$ are
$5^{+}$-faces. By R6, $v$ receives $\frac{1}{9}$ from its each incident
$5^{+}$-faces. Thus, $\mu^{*}(v)\geq 0$ after $v$ sends $\frac{1}{3}$ to its
each incident $3$-face by R1, $\frac{1}{9}$ to its $3$-neighbour by R2, and
$\frac{1}{15}$ to its $4$-neighbour by R7(a).

(3.3). Let $n_{3}(v)=0$. Namely, all neighbours of $v$ are $4^{+}$-vertices.
By Lemma 2.12, we have $m_{3}(v)\leq 4$. If $m_{3}(v)\leq 1$, then
$\mu^{*}(v)\geq 0$ after $v$ sends $\frac{1}{3}$ to its each incident $3$-face
by R1 and at most $\frac{2}{15}$ to its each $4$-neighbour by R7. So we may
assume that $2\leq m_{3}(v)\leq 4$.

(3.3.1). Let $m_{3}(v)=2$. Let $f_{1},f_{2}$ be $3$-faces. Notice that $v$ is
incident to three $5^{+}$-faces when all neighbours of $v$ are $4$-vertices by
Lemma 2.15(a). First of all, by R5, $v$ receives $\frac{1}{5}$ from its each
incident $5^{+}$-face. If $f_{1}$ and $f_{2}$ are non-adjacent, then
$\mu^{*}(v)\geq 0$ after $v$ sends $\frac{1}{3}$ to its each incident $3$-face
by R1, $\frac{1}{15}$ to its each $4$-neighbour incident to $f_{1}$ or $f_{2}$
by R7(a), $\frac{2}{15}$ to its $4$-neighbour incident to neither $f_{1}$ nor
$f_{2}$ by R7(b). We further assume that $f_{1}$ and $f_{2}$ are adjacent, say
$f_{1}=v_{1}vv_{2}$ and $f_{2}=v_{2}vv_{3}$. If $v$ is not a support vertex,
then $\mu^{*}(v)\geq 0$ after $v$ sends $\frac{1}{3}$ to its each incident
$3$-face by R1, $\frac{1}{15}$ to its each $4$-neighbour incident to $f_{1}$
or $f_{2}$ by R7(a), $\frac{2}{15}$ to its each $4$-neighbour incident to
neither $f_{1}$ nor $f_{2}$ by R7(b). We now assume that $v$ is a support
vertex. Then $v_{2}$ is a bad or a semi-bad vertex, which implies that $v_{2}$
has at most one $4$-neighbour by Remark 2.17, and thus $v$ has at most three
$4$-neighbours. Notice that the rule R7 cannot be applied for $v$ when it is
not incident to any $5^{+}$-face. In fact, if $v$ is not incident to any
$5^{+}$-face, then $\mu^{*}(v)\geq 0$ after $v$ sends $\frac{1}{3}$ to its
each incident $3$-face by R1, $\frac{1}{3}$ to $v_{2}$ by R10. Therefore we
suppose that $v$ is incident to a $5^{+}$-face. By R5, $v$ receives
$\frac{1}{5}$ from its each incident $5^{+}$-face. If $v$ is incident to only
one $5^{+}$-face, then $\mu^{*}(v)\geq 0$ after $v$ sends $\frac{1}{3}$ to its
each incident $3$-face by R1, $\frac{1}{3}$ to $v_{2}$ by R10, and
$\frac{1}{15}$ to its each $4$-neighbour by R7(a). If $v$ is incident to two
$5^{+}$-faces, then $v$ receives totally at least $2\times\frac{1}{5}$ from
its incident $5$-faces, and so $\mu^{*}(v)\geq 0$ after $v$ sends
$\frac{1}{3}$ to its each incident $3$-face by R1, $\frac{1}{3}$ to $v_{2}$ by
R10, and at most $\frac{2}{15}$ to its each $4$-neighbour by R7.

(3.3.2). Let $m_{3}(v)=3$. Let $f_{1},f_{2},f_{3}$ be $3$-faces. Notice that
$v$ can have at most three $4$-neighbours by Lemma 2.15(a).

Suppose first that $v$ is a strong vertex. Then we may assume that
$f_{1}=v_{1}vv_{2}$, $f_{2}=v_{2}vv_{3}$, and $f_{3}=v_{4}vv_{5}$. Recall that
$v$ is incident to a $5^{+}$-face, and $v_{2}$ is a bad or semi-bad vertex. By
R5, the vertex $v$ receives $\frac{1}{5}$ from its each incident $5^{+}$-face.
Notice that if $v$ has two $4$-neighbours, then $v$ would have two
$5^{+}$-faces by Lemma 2.20(a). In this case, $v$ receives totally
$2\times\frac{1}{5}$ from its incident $5^{+}$-faces. Thus, $\mu^{*}(v)\geq 0$
after $v$ sends $\frac{1}{3}$ to its each incident $3$-face by R1, at most
$\frac{1}{5}$ to $v_{2}$ by R8, and $\frac{1}{15}$ to its each $4$-neighbour
by R7(a) (if exists). Assume further that $v$ has at most one $4$-neighbour.
If $v_{2}$ has two common neighbours with only one of $v_{1},v_{3}$, then
$\mu^{*}(v)\geq 0$ after $v$ sends $\frac{1}{3}$ to its each incident $3$-face
by R1, $\frac{2}{15}$ to $v_{2}$ by R8(a), and $\frac{1}{15}$ to its
$4$-neighbour by R7(a) (if exists). If $v_{2}$ has two common neighbours with
each of $v_{1},v_{3}$, then either $v$ has no $4$-neighbour or $v$ is incident
to two $5^{+}$-face by Lemma 2.20(b). For each case, we have $\mu^{*}(v)\geq
0$ after $v$ sends $\frac{1}{3}$ to its each incident $3$-face by R1,
$\frac{1}{5}$ to $v_{2}$ by R8(b), and $\frac{1}{15}$ to its each
$4$-neighbour by R7(a) (if exists).

Next we suppose that $v$ is a good vertex. Then we have $f_{1}=v_{1}vv_{2}$,
$f_{2}=v_{2}vv_{3}$, and $f_{3}=v_{3}vv_{4}$ such that $v_{2}$ is a semi-bad
vertex, and each of $v_{1}v_{2},v_{2}v_{3}$ is contained in two $3$-faces.
Also, $v$ has at most one $4$-neighbour, and $v$ is incident to a $5^{+}$-face
by Lemma 2.22(b)-(c). If $v$ has a $4$-neighbour, then $f_{4},f_{5}$ are
$5^{+}$-faces Lemma 2.22(d). It follows from Proposition 2.21 that only one of
$v_{2},v_{3}$ can be semi-bad vertex. By R5, the vertex $v$ receives
$\frac{1}{5}$ from each $f_{4},f_{5}$. Thus $\mu^{*}(v)\geq 0$ after $v$ sends
$\frac{1}{3}$ to its each incident $3$-face by R1; $\frac{1}{5}$ to $v_{2}$ by
R9; at most $\frac{2}{15}$ to its $4$-neighbour by R7. Suppose next that $v$
has no $4$-neighbour. If $v_{3}$ is not a semi-bad vertex so that each of
$v_{2}v_{3},v_{3}v_{4}$ is contained in two $3$-faces, then $v$ receives
$\frac{1}{5}$ from its incident $5$-face by R5, and sends $\frac{1}{5}$ to
$v_{2}$ by R9. Consequently, $\mu^{*}(v)\geq 0$ after $v$ sends $\frac{1}{3}$
to its each incident $3$-face by R1. If $v_{3}$ is a semi-bad vertex so that
each of $v_{2}v_{3},v_{3}v_{4}$ is contained in two $3$-faces, then $v$ is
incident to two $5^{+}$-faces by Lemma 2.22(e). It follows from applying R5
that $v$ receives $\frac{1}{5}$ from its each incident $5^{+}$-face, and sends
$\frac{1}{5}$ to each $v_{2},v_{3}$ by R9. Consequently, $\mu^{*}(v)\geq 0$
after $v$ sends $\frac{1}{3}$ to its each incident $3$-face by R1.

Finally, suppose that $v$ is neither a strong nor a good vertex. Notice that
the rule R7 cannot be applied for $v$ when it is not incident to any
$5^{+}$-face. So, if none of $f_{4},f_{5}$ is a $5^{+}$-face, then
$\mu^{*}(v)\geq 0$ after $v$ sends $\frac{1}{3}$ to its each incident $3$-face
by R1. If only one of $f_{4},f_{5}$ is a $5^{+}$-face, then $v$ receives
$\frac{1}{5}$ from its incident $5$-face by R5, and sends $\frac{1}{15}$ to
its each $4$-neighbour by R7(a) (if exists). If both $f_{4}$ and $f_{5}$ are
$5^{+}$-faces, then $v$ receives $\frac{1}{5}$ from its each incident $5$-face
by R5, and sends at most $\frac{2}{15}$ to its each $4$-neighbour by R7 (if
exists). Consequently, $\mu^{*}(v)\geq 0$ after $v$ sends $\frac{1}{3}$ to its
each incident $3$-face by R1.

(3.3.3). Let $m_{3}(v)=4$. Let $f_{1},f_{2},f_{3},f_{4}$ be $3$-faces such
that $f_{i}=v_{i}vv_{i+1}$ for $i\in[4]$. We first observe that if $v$ is not
incident to any $5^{+}$-face, then $v$ cannot have any $4$-neighbour by Lemma
2.16(b). Moreover, $v$ cannot have more than one $4$-neighbour by Lemma
2.16(a). The vertex $v$ is a bad or a semi-bad vertex, we distinguish two
cases accordingly.

(3.3.3.1). Let $v$ be a bad vertex, i.e., $f_{5}$ is a $4$-face. By Remark
2.17(a), all neighbours of $v$ are $5$-vertices, also there is no edge
$v_{i}v_{i+1}$ for $i\in[4]$ contained in two $3$-faces. If one of
$v_{2},v_{3},v_{4}$ is incident to only two $3$-faces, then it must be a
support vertex, and so it gives $\frac{1}{3}$ to $v$ by R10. It follows that
$\mu^{*}(v)\geq 0$ after $v$ sends $\frac{1}{3}$ to its each incident $3$-face
by R1. Therefore, we may further assume that each of $v_{2},v_{3},v_{4}$ is
incident to exactly three $3$-faces, since no edge $v_{i}v_{i+1}$ for
$i\in[4]$ is contained in two $3$-faces. By Lemma 2.19(b), $v_{3}$ is a strong
vertex. This particularly implies that $v_{3}$ is incident to a $5^{+}$-face
$f_{j}$. We assume, without loss of generality, that $v_{2}v_{3}$ is an edge
of $f_{j}$. This means that both $v_{2}$ and $v_{3}$ are strong vertices. It
follows that $v$ receives $\frac{1}{5}$ from $v_{3}$ by R8(b), and
$\frac{2}{15}$ from $v_{2}$ by R8(a). Consequently, $\mu^{*}(v)\geq 0$ after
$v$ sends $\frac{1}{3}$ to its each incident $3$-face by R1.

(3.3.3.2). Let $v$ be a semi-bad vertex, i.e., $f_{5}$ is a $5^{+}$-face. By
R5, $v$ receives $\frac{1}{5}$ from $f_{5}$.

Suppose first that there is no edge $v_{i}v_{i+1}$ for $i\in[4]$ contained in
two $3$-faces. It follows from Lemma 2.19(a) that $v_{2},v_{3},v_{4}$ are
$5$-vertices. If one of $v_{2},v_{3},v_{4}$ is incident to only two $3$-faces,
then it must be support vertex, and so it gives $\frac{1}{3}$ to $v$ by R10.
Thus we have $\mu^{*}(v)\geq 0$ after $v$ sends $\frac{1}{3}$ to its each
incident $3$-face by R1. We therefore assume that each of $v_{2},v_{3},v_{4}$
is incident to exactly three $3$-faces, since no edge $v_{i}v_{i+1}$ for
$i\in[4]$ is contained in two $3$-faces. By Lemma 2.19(c), $v_{3}$ is a strong
or a good vertex. However, the latter is not possible since no edge
$v_{i}v_{i+1}$ for $i\in[4]$ is contained in two $3$-faces. So $v_{3}$ is a
strong vertex, and it gives $\frac{1}{5}$ to $v$ by R8(b). Recall that $v$ has
already received $\frac{1}{5}$ from $f_{5}$. Consequently, $\mu^{*}(v)\geq 0$
after $v$ sends $\frac{1}{3}$ to its each incident $3$-face by R1.

We now suppose that there is an edge $v_{i}v_{i+1}$ for $i\in[4]$ contained in
two $3$-faces. The uniqueness of $v_{i}v_{i+1}$ follows from Lemma 2.16(d).
First consider the case that $v_{1}v_{2}$ is contained in two $3$-faces. If
$v_{3}$ is incident to only two $3$-faces, then it must be support vertex by
Lemma 2.19(c), and so it gives $\frac{1}{3}$ to $v$ by R10. Thus we have
$\mu^{*}(v)\geq 0$ after $v$ sends $\frac{1}{3}$ to its each incident $3$-face
by R1. So we may assume that $v_{3}$ is incident to exactly three $3$-faces by
Lemma 2.16(d). It follows from Lemma 2.19(c) that $v_{3}$ is a strong or a
good vertex. The latter is not possible since $v_{1}v_{2}$ is contained in two
$3$-faces, and only one of $vv_{i}$’s is contained in two $3$-faces Lemma
2.16(d). Thus, $v$ is a strong vertex, and $v$ receives at least $\frac{1}{5}$
from $v_{3}$ by R8 and R9. Consequently, $\mu^{*}(v)\geq 0$ after $v$ sends
$\frac{1}{3}$ to its each incident $3$-face by R1. Let us assume that
$v_{2}v_{3}$ is contained in two $3$-faces. In this case, $v_{3}$ is a good
vertex Lemma 2.19(c). It follows from applying R9 that $v$ receives
$\frac{1}{5}$ from $v_{3}$. Consequently, $\mu^{*}(v)\geq 0$ after $v$ sends
$\frac{1}{3}$ to its each incident $3$-face by R1.

## References

  * [1] Aoki, K. Improved 2-distance coloring of planar graphs with maximum degree 5. arXiv preprint arXiv:2307.16394, 2023.
  * [2] Hou, J., Jin, Y., Miao, L., and Zhao, Q. Coloring squares of planar graphs with maximum degree at most five. Graphs and Combinatorics, 39(2), 20, 2023.
  * [3] Chen, M., Miao, L., and Zhou, S. 2-distance coloring of planar graphs with maximum degree 5. Discrete Mathematics, 345(4), 112766, 2022.
  * [4] Cranston, D. W. Coloring, List Coloring, and Painting Squares of Graphs (and other related problems), The Electronic Journal of Combinatorics, 30, 2, DS25, (2022).
  * [5] Hartke, S. G., Jahanbekam, S. and Thomas, B., The chromatic number of the square of subcubic planar graphs. arXiv preprint arXiv:1604.06504, (2016).
  * [6] Heuvel, J. van den, McGuinness, S., Coloring of the square of planar graph, Journal of Graph Theory, 42 110–124, (2003).
  * [7] Molloy, M. and Salavatipour, M. R.,  A bound on the chromatic number of the square of a planar graph, Journal of Combinatorial Theory Series B, 94, 189–213, (2005).
  * [8] Thomassen, C., The square of a planar cubic graph is 7-colorable. Journal of Combinatorial Theory Series B, 128:192–218, (2018).
  * [9] Wegner, G., Graphs with given diameter and a coloring problem. Technical report, University of Dormund, (1977).
  * [10] West, D. B. Introduction to graph theory, volume 2. Prentice hall Upper Saddle River, 2001.
  * [11] Zhu B. $L(1,1)$-Labelling of graphs, Doctor Thesis, Zhejiang Normal University, 2012.
  * [12] Zhu, B., Bu, Y. Minimum 2-distance coloring of planar graphs and channel assignment, J. Comb. Optim. 36 55–64, 2018.
  * [13] Zou, J., Han, M., and Lai, H. J. Square Coloring of Planar Graphs with Maximum Degree at Most Five. arXiv preprint arXiv:2308.01824, 2023.