Injective coloring of planar graphs with girth 5

1.   Introduction

All graphs considered in this paper are finite simple graphs. For a planar graph $G$, we use $V(G)$, $E(G)$, $F(G)$, $\Delta(G)$, $\delta(G)$, $g(G)$ and $d_G(u, v)$ to denote its vertex set, edge set, face set, maximum degree, minimum degree, girth and the distance between $u$ and $v$ in graph $G$, respectively. For a vertex $v \in V\left(G \right)$, we use $k$ ($k^+$ or $k^-$)-vertex to denote a vertex of degree $k$ (at least $k$ or at most $k$). A $k$ ($k^+$ or $k^-$)-face is defined similarly. A $k$-neighbor of $v$ is a $k$-vertex adjacent to $v$. For $f \in F\left(G \right)$, we use $b(f)$ to denote the boundary walk of $f$ and write $f = [x_1x_2\cdots x_k]$ if $x_1, x_2, \cdots, x_k$ are the vertices of $b(f)$ in the clockwise order.

An injective $k$-coloring of a graph $G$ is a vertex coloring $c: \; V\left(G \right) \to \left\{ {1, 2, \cdots, k} \right\}$ such that $c\left(u \right) \ne c\left(v \right)$ if $u$ and $v$ have a common neighbor. The injective chromatic number of $G$, denoted by ${\chi _i}\left(G \right)$, is the least integer $k$ such that $G$ has an injective $k$-coloring.

The idea of injective coloring was introduced by Hahn et al. ^[1]. They proved the inequality $\Delta \le {\chi _i}(G) \le {\Delta ^2} - \Delta + 1$ for any planar graph $G$ with maximum degree $\Delta$. For planar graph $G$ with $g\left(G \right) \ge 4$, there are fewer results, Bu et al. ^[2] proved that ${\chi _i}\left(G \right) \le \Delta + 6$ if $\Delta \ge 20$ and 4-cycle and 4-cycle are disjoint. For planar graph $G$ with $g\left(G \right) \ge 5$, Bu and Lu ^[3] proved that $\chi_{i}(G)\leq\Delta+7$; then Dong and Lin ^[4] improved this result to $\chi_{i}(G)\leq\Delta+6$; Lu$\breve{z}$ar et al ^[5] proved that $\chi_{i}(G)\leq\Delta+4$ if $\Delta\geq439$; recently, Bu and Huang ^[6] showed that $\chi_{i}(G)\leq\Delta+4$ if $\Delta\geq11$; Bu and Ye ^[7] improved this upper bound to $\Delta+3$ when $\Delta\geq20$. For planar graph $G$ with $g\left(G \right) \ge 6$, Dong and Lin ^[8] proved that $\chi_{i}(G)\leq\Delta+2$ if $\Delta\geq9$ and $\chi_{i}(G)\leq\Delta+1$ if $\Delta\geq17$. In ^[9], Borodin et al proved that for every planar graph $G$, $\chi_{i}(G) = \Delta$ in each of the following cases (i-iv): (i) $g(G) = 7$ and $\Delta\geq16$; (ii) $8\leq g(G)\leq9$ and $\Delta\geq10$; (iii) $10\leq g(G)\leq11$ and $\Delta\geq6$; (iv) $g(G)\geq13$ and $\Delta = 5$.

In this paper, we consider the injective chromatic number of planar graph $G$ with $g(G)\geq5$ and prove the following theorem.

Theorem 1.1. If $G$ is a planar graph with $g(G)\geq5$, $\Delta \left(G \right) \ge 20$ and without adjacent 5-cycles, then $\chi_i(G)\leq\Delta(G)+2$.

2.   Proof of Theorem 1.1

2.1.   The properties of minimal counterexample

Let $G$ be a graph. If $G$ can not admit any injective coloring with $k$ colors, but any subgraph of $G$ can, then we call $G$ is injective $k$-critical. In this section, we assume $G$ is injective $k$-critical. We give some structural properties of $G$.

For convenience, we give out some notations. For a $k$-vertex $v$, let $N(v) = \{v_{1}, v_{2}, \cdot\cdot\cdot, v_{k}\}$ with $d(v_{1})\leq d(v_{2})\leq\cdot\cdot\cdot\leq d(v_{k})$, $D(v) = \sum\limits_{i = 1}^{k}d(v_{i})$, ${N^2}\left(v \right) = { \cup _{1 \le i \le k}}\left({N\left({{v_i}} \right)\backslash \left\{ v \right\}} \right)$. We use $n_{k}(v)$ to denote the number $k$-vertices in $N(v)$. If $d\left({{v_1}} \right) = 2$, then let $N\left({{v_1}} \right) = \left\{ {v, {{v'}_1}} \right\}$. A $2$-vertex or $4^+$-vertex $v$ of $G$ is called a heavy vertex or is heavy if $D(v)\geq \Delta+2+d(v)$, otherwise $v$ is called a light vertex or is light. A $3$-vertex $v$ of $G$ is called a heavy vertex or is heavy if $D\left(v \right) \ge \Delta + 2 + d\left(v \right)$ and ${n_2}\left(v \right) = 0$. Conversely, a $3$-vertex $v$ is called a light vertex or is light if $D\left(v \right) \le \Delta + 1 + d\left(v \right)$ and ${n_2}\left(v \right) = 0$. We use $n_k^l(v)$ and $n_k^h(v)$ to denote the number of adjacent light and heavy k-vertices of $v$, respectively. For a partial vertex coloring $c$ of $G$, we use $F(v)$ to denote the forbidden colors for $v$. Let $C = \{1, 2, \cdot\cdot\cdot, \Delta+2\}$ be a color set. For integers $k$ and $n$, a $k(n)$-vertex is a $k$-vertex adjacent to $n \; 2$-vertices. Now, we discuss the structures of $G$.

Lemma 2.1. Let $uv\in E(G)$. If $D\left(u \right) \le \Delta + 1 + d\left(u \right)$, then $D\left(v \right) \ge \Delta + 2 + d\left(v \right)$.

Proof. By contradiction, suppose $D\left(v \right) \le \Delta + 1 + d\left(v \right)$. By the minimality of $G$, $G-uv$ admits an injective coloring with $\Delta + 2$ colors. Erase the colors on $u$ and $v$. Since $D\left(u \right) \le \Delta + 1 + d\left(u \right)$ and $D\left(v \right) \le \Delta + 1 + d\left(v \right)$, we have $\left| {F\left(u \right)} \right| \le \Delta + 1$, $\left| {F\left(v \right)} \right| \le \Delta + 1$. Let $c\left(u \right) \in C - F\left(u \right)$ and $c\left(v \right) \in C - F\left(v \right)$, then $G$ has an injective $(\Delta + 2)$-coloring, a contradiction.

Based on Lemma 2.1, we can obtain the following two lemmas.

Lemma 2.2. $\delta(G) \geq 2$ and $G$ contains no adjacent $2$-vertices.

Lemma 2.3. Let $v$ be a $3(1)$-vertex of $G$ with $N\left(v \right) = \left\{ {{v_1}, {v_2}, {v_3}} \right\}$, where $d\left({{v_1}} \right) = 2$, then $d\left({{v_2}} \right) + d\left({{v_3}} \right) \ge \Delta + 3$.

Lemma 2.4. $G$ contains no adjacent $3(1)$-vertices.

Proof. By contradiction, suppose that there exists two adjacent 3(1)-vertices $u$ and $v$. Let ${u_1} \in N\left(u \right)$ and ${v_1} \in N\left(v \right)$ be two $2$-vertices. By the minimality of $G$, $G-uu_1$ admits an injective coloring with $\Delta + 2$ colors. We erase the colors on $u$, $v_1$ and $u_1$. First, we can color $u$ since $\left| {F\left({u} \right)} \right| \le \Delta + 1$. Then $\left| {F\left({v_1} \right)} \right| \le \Delta + 1$, $\left| {F\left({u_1} \right)} \right| \le \Delta + 1$, so we can color $v_1$ and $u_1$ in turn to get an injective $(\Delta + 2)$-coloring of $G$, a contradiction.

Lemma 2.5. If $f = \left[ { \cdots u{v_1}v{v_2}x \cdots } \right]$, $v$ is a light 3-vertex, $v_1$ and $v_2$ are $3(1)$-vertices, $d(u) = 2$, then $f$ is a $6^+$-face.

Proof. Suppose that the lemma is not true. Assume that $f = \left[ {u{v_1}v{v_2}x} \right]$ is a 5-face, then $d(x) = \Delta$ by Lemmas 2.1 and 2.2. By the minimality of $G$, $G-vv_2$ admits an injective coloring with $\Delta + 2$ colors. We erase the colors on $v$, $v_2$ and $u$. Since $\left| {F\left({{v_2}} \right)} \right| \le \Delta - 2 + 1 + 2 = \Delta + 1$ and $\left| {F\left(u \right)} \right| \le \Delta - 1 + 1 = \Delta$, we can color $v_2$ and $u$. Finally, $\left| {F\left(v \right)} \right| \le \Delta + 1$ since $v$ is a light 3-vertex, we can color $v$, a contradiction.

2.2.   Discharging

In this section, we prove Theorem 1.1 by contradiction. Let $G$ be a minimal counterexample of Theorem 1.1.

Applying Eulers formula $|V|+|F|-|E| = 2$ and the fact $\sum\limits_{v\in V(G)}d(v) = \sum\limits_{f\in F(G)}d(f) = 2|E(G)|$ for a plane graph, we have

Design a weight function $\omega \left(x \right)$ such that $\omega \left(x \right) = \frac{3}{2}d\left(x \right) - 5$ for each $x \in V\left(G \right)$, $\omega \left(x \right) = d\left(x \right) - 5$ for each $x \in F\left(G \right)$. Hence, $\sum\limits_{x\in V(G)\bigcup F(G)}\omega(x) = -10$. Next, we shall transfer weight. Our discharging procedure has two steps. Now, let's look at the structural properties of $G$, while keeping the total weight sum constant, we obtain a new weight $w^{'}(x)$ for all $x\in V\cup F$ by transferring weights after the first step. We shall prove that $w^{*}(x)\geq0$ for each $x\in V\cup F$ after the second step and then get the following contradiction:

This contradiction shows that $G$ does not exist and thus Theorem 1.1 is true.

$The \; first \; step$

We define the following discharging rules.

R10. Every vertex $v$ with $d\left(v \right) \ge 10$ sends $\frac{{\rm{3}}}{2}{\rm{ - }}\frac{{\rm{5}}}{{d\left(v \right)}}$ to each adjacent $9^-$-vertex.

R11. Let $v$ be a 2-vertex with $N\left(v \right) = \left\{ {{v_1}, {v_2}} \right\}$. If $d\left({{v_1}} \right) \le d\left({{v_2}} \right) \le 9$, then ${v_i}\left({i = 1, 2} \right)$ sends $\frac{11}{12}$ to $v$. If $d\left({{v_1}} \right) \le 9 < d\left({{v_2}} \right)$, then $v_1$ sends $\frac{1}{3} + \frac{5}{{d\left({{v_2}} \right)}}$ to $v$.

R12. Let $v$ be a $3(1)$-vertex with $N\left(v \right) = \left\{ {{v_1}, {v_2}, {v_3}} \right\}$. If $d(v_1) = 2$, $3 \le d\left({{v_2}} \right) \le 9$, and $d\left({{v_3}} \right) \le 20$, then $v_2$ sends $\frac{5}{{d\left({{v_3}} \right)}} - \frac{1}{4}$ to $v$.

R13. Every heavy vertex $v$ with $3\leq d(v)\leq 9$ sends $\frac{1}{{3}}$ to each adjacent light 3-vertex.

R14. Each of 8-vertex and 9-vertex sends $\frac{1}{{6}}$ to every adjacent heavy 3-vertex.

R15. Every $6^+$-face sends $\frac{{d\left(f \right) - 5}}{{d\left(f \right)}}$ to each incident $9^-$-vertex.

Let $\omega '\left(x \right)$ be the new weight of each $x\in V \cup F$ by applying the above rules. Let $v$ be a $k$-vertex. Note that $k \ge 2$ by Lemma 2.2. By $R10$, every $10^+$-vertex sends at least 1 to each adjacent $9^-$-vertex.

(1) $k = 2$, $w(v) = -2$.

If $d\left({{v_1}} \right) \le d\left({{v_2}} \right) \le 9$, then ${v_i}(i = 1, 2)$ sends $\frac{{11}}{{12}}$ to $v$. If $d\left({{v_1}} \right) \le 9 < d\left({{v_2}} \right)$, then $v_1$ sends $\frac{1}{3} + \frac{5}{{d\left({{v_2}} \right)}}$ to $v$, $v_2$ sends $\frac{3}{2} - \frac{5}{{d\left({{v_2}} \right)}}$ to $v$ by R10 and R11. If $10 \le d\left({{v_1}} \right) \le d\left({{v_2}} \right)$, then ${v_i}$ sends $\frac{3}{2} - \frac{5}{{d\left({{v_i}} \right)}}(i = 1, 2)$ to $v$ by R10. By R15, $6^+$-face sends at least $\frac{{1}}{{6}}$ to $v$. Hence,

(2) $k = 3$, $\omega (v) = -\frac{1}{2}$.

Case 1. Suppose that $v$ is a $3(1)$-vertex. By Lemma 2.3, $d\left({{v_2}} \right) + d\left({{v_3}} \right) \ge \Delta + 3 \ge 23$. Note that $v$ is adjacent to at least a $12^+$-vertex and $d\left({{v_2}} \right) \ge 3$. If $3 \le d\left({{v_2}} \right) \le 9$, then $d\left({{v_3}} \right) \ge \Delta - 6$. By R10, R11, R12 and R15, $\omega '\left(v \right) \ge - \frac{1}{2} - \frac{{11}}{{12}} + \frac{1}{6} \times 2 + \frac{5}{{d\left({{v_3}} \right)}} - \frac{1}{4} + \frac{3}{2} - \frac{5}{{d\left({{v_3}} \right)}} = \frac{1}{6}$ when $d(v_3) \le 20$; $\omega '\left(v \right) \ge - \frac{1}{2} - \frac{{11}}{{12}} + \frac{1}{6} \times 2 + \frac{3}{2} - \frac{5}{{d\left({{v_3}} \right)}} \ge \frac{5}{{28}}$ when $d(v_3) \ge 21$. If $d\left({{v_3}} \right) \ge d\left({{v_2}} \right) \ge 10$, then $\omega '\left(v \right) \ge - \frac{1}{2} - \frac{{11}}{{12}} + \frac{3}{2} - \frac{5}{{d\left({{v_2}} \right)}} + \frac{3}{2} - \frac{5}{{d\left({{v_3}} \right)}} + \frac{1}{6} \times 2 > 0$ by R10, R11 and R15.

Case 2. Supose that $v$ is a heavy 3-vertex. Note that $D\left(v \right) \ge \Delta + 2 + 3 \ge 25$, $v$ is a (8, 8, 9)-vertex or ($d_1$, 9, 9)-vertex($7\le d_1 \le 9$) or ($d_1$, $d_2$, $10^+$)-vertex($d_1 \le d_2 \le 10$). By R13, a heavy 3-vertex sends at most $\frac{1}{3}$ to a light 3-vertex. Hence, $\omega '\left(v \right) \ge - \frac{1}{2} + \min \left\{ {\frac{1}{6} \times 3, \frac{1}{6} \times 2, 1 - \frac{1}{3} \times 2} \right\} + \frac{1}{6} \times 2 > 0$ by R10, R14 and R15.

Case 3. Suppose that $v$ is a light 3-vertex. If $v$ is adjacent to a $3(1)$-vertex $u$, then $u$ is adjacent to a $\Delta$-vertex by Lemma 2.3. If $\Delta = 20$, then $v$ sends $\frac{5}{\Delta } - \frac{1}{4} = 0$ to $u$. Otherwise, $v$ sends nothing to $u$. If $v$ is adjacent to at least one $10^+$-vertex, then $\omega '\left(v \right) \ge - \frac{1}{2} - \left({\frac{5}{\Delta } - \frac{1}{4}} \right) + 1 + \frac{1}{6} \times 2 > 0$ by R10, R12 and R15. If $v$ is adjacent to at most two $3(1)$-vertices and not adjacent to $10^+$-vertex, then $\omega '\left(v \right) \ge - \frac{1}{2} + \frac{1}{3} + \frac{1}{6} \times 2 > 0$ by R12, R13 and R15. Finally, $v$ is adjacent to three $3(1)$-vertices. If $v$ is incident with three $6^+$-faces or a 5-face, two $7^+$-faces or a 5-face, at least a $8^+$-face, then $\omega '\left(v \right) \ge - \frac{1}{2} + \min \left\{ {\frac{1}{6} \times 3, \frac{2}{7} \times 2, \frac{1}{6} + \frac{3}{8}} \right\} > 0$ by R15. If $v$ is incident with a 5-face, two 6-faces or a 5-face, a 6-face and a 7-face, then $\omega '\left(v \right) = -\frac{1}{6}$ or $\omega '\left(v \right) = -\frac{1}{12}$ by R15.

(3) $k = 4$, $\omega (v) = 1$.

Case 1. ${n_2}\left(v \right) = 0$. By Lemma 2.3, the 3(1)-neighbor $u$ of $v$ is adjacent to a ${\left({\Delta - 1} \right)^ + }$-vertex. If $u$ is adjacent to a $21^+$-vertex, then $v$ sends 0 to $u$. Suppose $v$ is adjacent to a $l$-vertex with $19 \le l \le 20$. By R12, $v$ sends at most $\frac{5}{19} - \frac{1}{4}$ to 3(1)-vertex. If $D\left(v \right) \le \Delta + 1 + 4$, then $v$ is light. Therefore, $\omega '\left(v \right) \ge 1 - 4 \times \left({\frac{5}{19} - \frac{1}{4}} \right) + \frac{1}{6} \times 2 > 0$ by R15. If $D\left(v \right) \ge \Delta + 6$, then $v$ is heavy. If $n_3^l\left(v \right) = 1$, then $\omega '\left(v \right) \ge 1 - 2 \times \left({\frac{5}{19} - \frac{1}{4}} \right) - \frac{1}{3} + \frac{1}{6} \times 2 > 0$ by R12, R13 and R15. If $n_3^l\left(v \right) \ge 2$, then $d\left({{v_3}} \right) + d\left({{v_4}} \right) \ge \Delta$. Hence, $v_4$ is a $10^+$-vertex. This implies that $\omega '\left(v \right) \ge 1 - \frac{1}{3} \times 3 + \left({\frac{3}{2} - \frac{5}{{d\left({{v_4}} \right)}}} \right) + \frac{1}{6} \times 2 > 0$ by R10, R13 and R15.

Case 2. ${n_2}\left(v \right) = 1$. If $D\left(v \right) \ge \Delta + 6$, then $v$ is heavy. If ${n_3}\left(v \right) = 0$, then $v$ only sends weight to 2-vertex. By R10, R11 and R15, $\omega '\left(v \right) \ge 1 - \frac{{11}}{{12}} + \frac{1}{6} \times 2 > 0$. If ${n_3}\left(v \right) = 1$, then $d\left({{v_3}} \right) + d\left({{v_4}} \right) \ge \Delta + 1$. Therefore, $v_4$ is a $11^+$-vertex. It follows from R10, R11, R13 and R15 that $\omega '\left(v \right) \ge 1 - \frac{{11}}{{12}} - \frac{1}{3} + \left({\frac{3}{2} - \frac{5}{{d\left({{v_4}} \right)}}} \right) + \frac{1}{6} \times 2 > 0$. If ${n_3}\left(v \right) = 2$, then $d\left({{v_4}} \right) \ge \Delta - 2$. This together with R10, R11, R13 and R15 implies that $\omega '\left(v \right) \ge 1 - \frac{{11}}{{12}} - \frac{1}{3} \times 2 + (\frac{3}{2} - \frac{5}{{\Delta - 2}})+ \frac{1}{6} \times 2 > 0$. Otherwise, $D\left(v \right) \le \Delta + 5$, then $v$ is light and the vertices adjacent to $v$ are all heavy. So the 2-neighbor $u$ of $v$ is adjacent to a $\Delta$-vertex and the 3(1)-neighbor of $v$ is adjacent to a $(\Delta - 1)^+$-vertex. If the 3(1)-neighbor of $v$ is adjacent to a $21^+$-vertex, then $v$ sends 0 to this 3(1)-vertex. This implies that $\omega '\left(v \right) \ge 1 - \left({\frac{1}{3} + \frac{5}{\Delta }} \right) - 3 \times \left({\frac{5}{{\Delta - 1}} - \frac{1}{4}} \right) + \frac{1}{6} \times 2 > 0$ by R11, R12 and R15.

Case 3. ${n_2}\left(v \right) = 2$. If $D\left(v \right) \ge \Delta + 6$, then $v$ is heavy. It follows from Lemma 2.1 that $d\left({{v_3}} \right) + d\left({{v_4}} \right) \ge \Delta + 2$, which means that $v_4$ is a $11^+$-vertex. Therefore, $\omega '\left(v \right) \ge 1 - \frac{{11}}{{12}} \times 2 + \min \left\{ { - \frac{1}{3} + \frac{3}{2} - \frac{5}{{\Delta - 1}}, \frac{3}{2} - \frac{5}{{11}}} \right\} + \frac{1}{6} \times\; 2 > 0$ by R10, R11, R13 and R15. Otherwise, $D\left(v \right) \le \Delta + 5$, then $v$ is light and the vertices adjacent to $v$ are all heavy. Hence, the 2-neighbor of $v$ is adjacent to a $\Delta$-vertex and the 3(1)-neighbor of $v$ is adjacent to a $(\Delta - 1)^+$-vertex. If the 3(1)-neighbor of $v$ is adjacent to a $21^+$-vertex, then $v$ sends 0 to this 3(1)-vertex. This together with R11, R12 and R15 yields that $\omega '\left(v \right) \ge 1 - \left({\frac{1}{3} + \frac{5}{\Delta }} \right) \times 2 - \left({\frac{5}{{\Delta - 1}} - \frac{1}{4}} \right) \times\; 2 + \frac{1}{6} \times 2 > 0$.

Case 4. ${n_2}\left(v \right) = 3$. If $D\left(v \right) \ge \Delta + 6$, then $v$ is heavy and $d\left({{v_4}} \right) = \Delta$. If the 2-vertices adjacent to $v$ are all light and $v$ is incident with at most a 5-face, then $\omega '\left(v \right) \ge 1 + \left({\frac{3}{2} - \frac{5}{\Delta }} \right) - \frac{{11}}{{12}} \times 3 + \frac{1}{6} \times 3 \ge 0$ by R10, R11 and R15. If the 2-vertices adjacent to $v$ are all light and $v$ is incident with two 5-faces, then $\omega '\left(v \right) \ge 1 + \frac{3}{2} - \frac{5}{\Delta } - \frac{{11}}{{12}} \times 3 + \frac{1}{6} \times 2 \ge - \frac{1}{6}$ by R10, R11 and R15. If the 2-vertices adjacent to $v$ are all heavy, then $\omega '\left(v \right) \ge 1 + \left({\frac{3}{2} - \frac{5}{\Delta }} \right) - \left({\frac{1}{3} + \frac{5}{\Delta }} \right) \times 3 + \frac{1}{6} \times 2 \ge \frac{5}{6}$ by R10, R11 and R15. If the 2-vertices adjacent to $v$ are not all light, let $v_1$ be a light 2-vertex, then we have that $\omega '\left(v \right) \ge 1 + \left({\frac{3}{2} - \frac{5}{\Delta }} \right) - \left({\frac{1}{3} + \frac{5}{\Delta }} \right) - \frac{{11}}{{12}} \times 2 + \frac{1}{6} \times 2 > 0$ by R10, R11 and R15. Otherwise, $D\left(v \right) \le \Delta + 5$, then $v$ is light and the vertices adjacent to $v$ are all heavy. Hence, the 2-neighbor of $v$ is adjacent to a $\Delta$-vertex and the 3(1)-neighbor of $v$ is adjacent to a $(\Delta - 1)^+$-vertex. If the 3(1)-neighbor of $v$ is adjacent to a $21^+$-vertex, then $v$ sends 0 to this 3(1)-vertex. This together with R11, R12 and R15 yields that $\omega '\left(v \right) \ge 1 - \left({\frac{1}{3} + \frac{5}{\Delta }} \right) \times 3 - \left({\frac{5}{{\Delta - 1}} - \frac{1}{4}} \right) + \frac{1}{6} \times 2 \ge - \frac{{49}}{{114}}$.

Case 5. ${n_2}\left(v \right) = 4$. Clearly, $D\left(v \right) \le \Delta + 5$, which implies that the 2-neighbor of $v$ is adjacent to a $\Delta$-vertex. By R11 and R15, $\omega '\left(v \right) \ge 1 - \left({\frac{1}{3} + \frac{5}{\Delta }} \right) \times 4 + \frac{1}{6} \times 2 \ge - 1$.

(4) $k = 5$, $\omega (v) = \frac{5}{2}$.

Case 1. ${n_2}\left(v \right) \le 2$. It follows from R11, R13 and R15 that $\omega '\left(v \right) \ge \frac{5}{2} - \frac{{11}}{{12}} \times 2 - \frac{1}{3} \times 3 + \frac{1}{6} \times 3 > 0$.

Case 2. ${n_2}\left(v \right) = 3$. If $D\left(v \right) \ge \Delta + 7$, then $v$ is heavy and $d\left({{v_4}} \right) + d\left({{v_5}} \right) \ge \Delta + 1$. Therefore, $v_5$ is a $11^+$-vertex. This means that $\omega '\left(v \right) \ge \frac{5}{2} - \frac{{11}}{{12}} \times 3 + \min \left\{ { - \frac{1}{3} + \left({\frac{3}{2} - \frac{5}{{\Delta - 2}}} \right), \frac{3}{2} - \frac{5}{{11}}} \right\} + \frac{1}{6} \times 3 > 0$ by R10, R11, R13 and R15. Otherwise, $D\left(v \right) \le \Delta + 6$, then $v$ is light and the vertices adjacent to $v$ are all heavy. So the 2-neighbor of $v$ is adjacent to a $(\Delta - 1)^+$-vertex and the 3(1)-neighbor of $v$ is adjacent to a $(\Delta - 2)^+$-vertex. If the 3(1)-neighbor of $v$ is adjacent to a $21^+$-vertex, then $v$ sends 0 to this 3(1)-vertex. By R11, R12 and R15, $\omega '\left(v \right) \ge \frac{5}{2} - \left({\frac{1}{3} + \frac{5}{{\Delta - 1}}} \right) \times 3 - \left({\frac{5}{{\Delta - 2}} - \frac{1}{4}} \right) \times 2 + \frac{1}{6} \times 3 > 0$.

Case 3. ${n_2}\left(v \right) = 4$. If $D\left(v \right) \ge \Delta + 7$, then $v$ is heavy and $d\left({{v_5}} \right) \ge \Delta - 1$. By R10, R11 and R15, $\omega '\left(v \right) \ge \frac{5}{2} - \frac{{11}}{{12}} \times 4 + \frac{3}{2} - \frac{5}{{\Delta - 1}} + \frac{1}{6} \times 3 > 0$. Otherwise, $D\left(v \right) \le \Delta + 6$, then $v$ is light and the vertices adjacent to $v$ are all heavy. Hence, the 2-neighbor of $v$ is adjacent to a $(\Delta - 1)^+$-vertex and the 3(1)-neighbor of $v$ is adjacent to a $(\Delta - 2)^+$-vertex. If the 3(1)-neighbor of $v$ is adjacent to a $21^+$-vertex, then $v$ sends 0 to this 3(1)-vertex. By R11, R12 and R15, $\omega '\left(v \right) \ge \frac{5}{2} - \left({\frac{1}{3} + \frac{5}{{\Delta - 1}}} \right) \times 4 - \left({\frac{5}{{\Delta - 2}} - \frac{1}{4}} \right) + \frac{1}{6} \times 3 > 0$.

Case 4. ${n_2}\left(v \right) = 5$. Clearly, $D\left(v \right) \le \Delta + 6$, which means that the 2-neighbor of $v$ is adjacent to a $(\Delta-1)^+$-vertex. So $\omega '\left(v \right) \ge \frac{5}{2} - \left({\frac{1}{3} + \frac{5}{{\Delta - 1}}} \right) \times 5 + \frac{1}{6} \times 3 > 0$ by R11 and R15.

(5) $k = 6$, $\omega (v) = 4$.

Case 1. ${n_2}\left(v \right) \le 4$. It is clear that $\omega '\left(v \right) \ge 4 - \frac{{11}}{{12}} \times 4 - \frac{1}{3} \times 2 + \frac{1}{6} \times 3 > 0$ by R11, R13 and R15.

Case 2. ${n_2}\left(v \right) = 5$. If $D\left(v \right) \ge \Delta + 8$, then $v$ is heavy and $d\left({{v_6}} \right) \ge \Delta - 2$. This together with R10, R11 and R15 implies that $\omega '\left(v \right) \ge 4 - \frac{{11}}{{12}} \times 5 + \frac{3}{2} - \frac{5}{{\Delta - 2}} + \frac{1}{6} \times 3 > 0$. Otherwise, $D\left(v \right) \le \Delta + 7$, then $v$ is light and the vertices adjacent to $v$ are all heavy. Therefore, the 2-neighbor of $v$ is adjacent to a $(\Delta - 2)^+$-vertex and the 3(1)-neighbor of $v$ is adjacent to a $(\Delta - 3)^+$-vertex. If the 3(1)-neighbor of $v$ is adjacent to a $21^+$-vertex, then $v$ sends 0 to this 3(1)-vertex. By R11, R12 and R15, $\omega '\left(v \right) \ge\; 4 - \left({\frac{1}{3} + \frac{5}{{\Delta - 2}}} \right) \times 5 - \left({\frac{5}{{\Delta - 3}} - \frac{1}{4}} \right) + \frac{1}{6} \times 3 > 0$.

Case 3. ${n_2}\left(v \right) = 6$. It is easy to see that $D\left(v \right) \le \Delta + 7$, which implies that the 2-neighbor of $v$ is adjacent to a $(\Delta-2)^+$-vertex. By R11 and R15, $\omega '\left(v \right) \ge 4 - \left({\frac{1}{3} + \frac{5}{{\Delta - 2}}} \right) \times 6 + \frac{1}{6} \times 3 > 0$.

(6) $k = 7$, $\omega (v) = \frac{11}{2}$.

Case 1. ${n_2}\left(v \right) \le 6$. By R11, R13 and R15, $\omega '\left(v \right) \ge \frac{{11}}{2} - \frac{{11}}{{12}} \times 6 - \frac{1}{3} + \frac{1}{6} \times 4 > 0$.

Case 2. ${n_2}\left(v \right) = 7$. It is clear that $D\left(v \right) \le \Delta + 7$, which means that the 2-neighbor of $v$ is adjacent to a $(\Delta-3)^+$-vertex. By R11 and R15, $\omega '\left(v \right) \ge \frac{{11}}{2} - \left({\frac{1}{3} + \frac{5}{{\Delta - 3}}} \right) \times 7 + \frac{1}{6} \times 4 > 0$.

(7) $k = 8$, $\omega (v) = 7$. Observe that $\omega '\left(v \right) \ge 7 - \frac{{11}}{{12}} \times 8 + \frac{1}{6} \times 4 > 0$ by R11, R13 and R15.

(8) $k = 9$, $\omega (v) = \frac{17}{2}$. By R11, R13 and R15, $\omega '\left(v \right) \ge \frac{{17}}{2} - \frac{{11}}{{12}} \times 9 + \frac{1}{6} \times 5 > 0$.

(9) $k \ge 10$, $\omega (v) = \frac{3}{2}k - 5$. By R10, $\omega '\left(v \right) \ge \frac{3}{2}k - 5 - \left({\frac{3}{2} - \frac{5}{{k}}} \right) \times k = 0$.

After the first step, $\omega '\left(x \right) \ge 0$ for each $x\in V \cup F$ except some 3-vertices and 4-vertices. For $f \in F\left(G \right)$, if $d\left(f \right) \ge 5$, then $\omega '\left(f \right) \ge \min \left\{ {0, d\left(f \right) - 5 - \frac{{d\left(f \right) - 5}}{{d\left(f \right)}} \cdot d\left(f \right)} \right\} = 0$ by R15. For convenience, a vertex $v$ is called $bad$ if $\omega '\left(v \right) < 0$. If $uv \in E\left(G \right)$ and $u$, $v$ are all ${10^ + }$-vertices, then $uv$ is called special edge.

There are four bad vertices:

I-vertex: 3-vertex $v$ is adjacent to three 3(1)-vertices and incident with a 5-face, two 6-faces or a 5-face, a 6-face and a 7-face, $\omega '\left(v \right) \ge - \frac{1}{6}$.

II-vertex: 4-vertex $v$ is adjacent to three light 2-vertices, a $\Delta$-vertex and incident with two 5-faces, $\omega '\left(v \right) \ge - \frac{1}{6}$.

III-vertex: light 4-vertex $v$ is adjacent to three 2-vertices, $\omega '\left(v \right) \ge - \frac{{49}}{{114}}$.

IV-vertex: 4-vertex $v$ is adjacent to four 2-vertices, $\omega '\left(v \right) \ge - 1$.

Obviously, bad vertex is not adjacent to bad vertex.

$The \; second \; step$

R20. Every $10^+$-vertex $v$ sends $\frac{1}{2}$ to incident face $f$ through its special edge.

R21. Every $9^-$-vertex sends its remained positive weight averagely to each incident face.

R22. Every $5^+$-face sends its remained positive weight averagely to each incident bad vertex.

(1) $v$ is I-vertex, see Figure 1a. Clearly, $v$ is a light 3-vertex. By Lemma 2.1, $D\left({{v_i}} \right) \ge \Delta + 5$, which means that $d\left({v'_i} \right) = \Delta$ for $1 \le i \le 3$.

Let ${f_1} = {v_1}v{v_2}xy$ be a 5-face with $d\left(x \right), d\left(y \right) \in \left\{ {2, \Delta } \right\}$, $f_2$ and $f_3$ be $6^+$-faces. By Lemma 2.2, at least one of $x$ and $y$ is not 2-vertex. Note that $\left\{ {d\left(x \right), d\left(y \right)} \right\} \ne \left\{ {2, \Delta } \right\}$ by Lemma 2.5. Hence, $d\left(x \right) = d\left(y \right) = \Delta$, which means that ${v'_1}{v'_2}$ is a special edge. By R20, $f_1$ receives $\frac{1}{2} \times 2$ from ${v'_1}, {v'_2}$. Obviously, $f_1$ is only incident with a bad vertex $v$, which together with R22 shows that ${\omega ^*}\left(v \right) \ge - \frac{1}{6} + 1 > 0$.

(2) $v$ is II-vertex, see Figure 1b. By Lemma 2.1, $D\left({{{v'}_i}} \right) \ge \Delta + 2 + d\left({{{v'}_i}} \right)$. Let $f_1$ and $f_3$ be 5-faces.

Case 1. If there is a bad vertex in $\left\{ {{v'_1}, {v'_2}, {v'_3}} \right\}$, then it can not be I, III, IV-vertex. If ${v'_1}$ is a bad vertex, then ${v'_2}$ is a $\Delta$-vertex by Lemma 2.2, which means that $v_2$ is a heavy 2-vertex, a contradiction. Hence, ${v'_1}$ can not be a bad vertex. Similarly, ${v'_2}$ can not be a bad vertex. Next, suppose that ${v'_3}$ is a bad vertex, see Figure 2a. If $u$ is a $2$-vertex, then $u$ is a heavy 2-vertex. This is contradict with II-vertex ${v'_3}$ only adjacent to light 2-vertex. If $u$ is a $\Delta$-vertex, then $uv_4$ is a special edge. By R20, $f_3$ gets 1 from $uv_4$. Obviously, $f_3$ is only incident with two bad vertices $v$ and ${v'_3}$, which implies that ${\omega ^*}\left(v \right) \ge - \frac{1}{6} + \frac{1}{2} > 0$ by R22.

Case 2. If ${v'_1}, {v'_2}, {v'_3}$ are not bad vertices, then $f_4$ is incident with at most $\left\lfloor {\frac{{d\left({{f_4}} \right) - 3}}{2}} \right\rfloor + 1$ bad vertices.

Case 2.1. Suppose that $f_4$ is a $7^+$-face. Since $d\left({{v_4}} \right) = \Delta$, we can get $\omega '\left({{f_4}} \right) \ge \frac{{d\left({{f_4}} \right) - 5}}{{d\left({{f_4}} \right)}}$. By the first step and R22, ${\omega ^*}\left(v \right) \ge 1 + \frac{3}{2} - \frac{5}{\Delta } - \frac{{11}}{{12}} \times 3 + \frac{{d\left({{f_4}} \right) - 5}}{{d\left({{f_4}} \right)}} + \frac{1}{6} + \frac{{d\left({{f_4}} \right) - 5}}{{d\left({{f_4}} \right)}} \times \frac{1}{{\left\lfloor {\frac{{d\left({{f_4}} \right) - 3}}{2}} \right\rfloor + 1}} > 0$.

Case 2.2. Suppose that $f_2$ is a $7^+$-face. Since $d\left({{v_4}} \right) = \Delta$, we can get $\omega '\left({{f_4}} \right) \ge \frac{{d\left({{f_4}} \right) - 5}}{{d\left({{f_4}} \right)}}$. By the first step and R22, ${\omega ^*}\left(v \right) \ge 1 + \frac{3}{2} - \frac{5}{\Delta } - \frac{{11}}{{12}} \times 3 + \frac{{d\left({{f_4}} \right) - 5}}{{d\left({{f_4}} \right)}} + \frac{2}{7} + \frac{{d\left({{f_4}} \right) - 5}}{{d\left({{f_4}} \right)}} \times \frac{1}{{\left\lfloor {\frac{{d\left({{f_4}} \right) - 3}}{2}} \right\rfloor + 1}} > 0$.

Case 2.3. Suppose that $f_2$ and $f_4$ are all 6-faces, see Figure 2b. It is easy to see that $f_2$ and $f_3$ are only incident with a bad vertex $v$, $f_4$ is incident with at most two bad vertices.

If ${v'_1}$ is a $10^+$-vertex, then $\omega '\left({{f_4}} \right) \ge \frac{1}{6} \times 2$ by $d\left({{v_4}} \right) = \Delta$. By R22, ${\omega ^*}\left(v \right) \ge - \frac{1}{6} + \frac{1}{6} \times \frac{1}{2} > 0$. If ${v'_2}$ is a $10^+$-vertex, then $\omega '\left({{f_2}} \right) \ge \frac{1}{6} \times 2$. By $d\left({{v_4}} \right) = \Delta$, $\omega '\left({{f_4}} \right) \ge \frac{1}{6}$. This means that ${\omega ^*}\left(v \right) \ge - \frac{1}{6} + \frac{1}{6} \times \frac{1}{2} + \frac{1}{6} > 0$ by R22. If ${v'_3}$ is a $10^+$-vertex, then $\omega '\left({{f_2}} \right) \ge \frac{1}{6}$. By $d\left({{v_4}} \right) = \Delta$, $\omega '\left({{f_4}} \right) \ge \frac{1}{6}$, which implies that ${\omega ^*}\left(v \right) \ge - \frac{1}{6} + \frac{1}{6} \times \frac{1}{2} + \frac{1}{6} > 0$.

If ${v'_1}, {v'_2}, {v'_3}$ are all $9^-$-vertices, then we discuss the classification of $d(x)$. We can obtain that $\omega '\left({{f_4}} \right) \ge \frac{1}{6}$ since $d\left({{v_4}} \right) = \Delta$.

If $d\left(x \right) \ge 10$, then $xv_4$ is a special edge. By R20, each of $x$ and $v_4$ sends $\frac{1}{2}$ to $f_3$. Hence, ${\omega ^*}\left(v \right) \ge - \frac{1}{6}+ \frac{1}{6} \times \frac{1}{2}+ 1 > 0$ by R22. If $5 \le d\left(x \right) \le 9$, then ${\omega ^{\rm{*}}}\left(x \right) \ge \frac{3}{2}d\left(x \right) - 5 + \left({\frac{3}{2} - \frac{5}{\Delta }} \right) - \frac{{11}}{{12}}\left({d\left(x \right) - 1} \right) + \frac{1}{6} \times \left\lceil {\frac{{d\left(x \right)}}{2}} \right\rceil \ge \frac{2}{3}d\left(x \right) - \frac{{17}}{6}$ by R10, R11 and R15. This means that $f_3$ gets $\left({\frac{2}{3}d\left(x \right) - \frac{{17}}{6}} \right)\frac{1}{{d\left(x \right)}} \ge \frac{1}{{10}}$ by R21. Hence, ${\omega ^*}\left(v \right) \ge - \frac{1}{6} + \frac{1}{6} \times \frac{1}{2} + \frac{{1}}{{10}} > 0$ by R22.

If $d\left(x \right) = 4$, then $\omega '\left(x \right) \ge 1 + \left({\frac{3}{2} - \frac{5}{\Delta }} \right) - \frac{{11}}{{12}} \times 2 - \left({\frac{5}{{\Delta - 1}} - \frac{1}{4}} \right) + \frac{1}{6} \times 2 = \frac{{14}}{{19}}$ by R10, R11, R12 and R15. This implies that $f_3$ gets $\frac{7}{38}$ by R21. Hence, ${\omega ^*}\left(v \right) \ge - \frac{1}{6} + \frac{1}{6} \times \frac{1}{2} + \frac{7}{{38}} > 0$ by R22. If $d\left(x \right) = 3$, then $\omega '\left(x \right) \ge - \frac{1}{2} + \left({\frac{3}{2} - \frac{5}{\Delta }} \right) - \frac{{11}}{{12}} + \frac{1}{6} \times 2 = \frac{1}{6}$ by R10, R11, R12 and R15. This means that $f_3$ gets $\frac{1}{18}$ by R21. Similarly, we consider the degree of $u$. If $d\left(u \right) \ge 3$, then $f_4$ gets at least $\min \left\{ {1, \frac{{1}}{{10}}, \frac{1}{{18}}} \right\} = \frac{1}{{18}}$. It follows from R22 that ${\omega ^*}\left(v \right) \ge - \frac{1}{6} + \frac{1}{6} \times \frac{1}{2} + \frac{1}{{18}} + \frac{1}{{18}} \times \frac{1}{2} = 0$. If $d(u) = 2$, then $f_4$ is only incident with a bad vertex $v$. By R22, ${\omega ^*}\left(v \right) \ge - \frac{1}{6} + \frac{1}{6} = 0$.

(3) $v$ is III-vertex, see Figure 1c. Observe that $d\left({{v'_i}} \right) = \Delta$ (i = 1, 2, 3) by Lemma 2.1.

Suppose that $f_1$ or $f_2$ is a 5-face. Without loss of generality, let $f_1$ be a 5-face, then ${v'_1}{v'_2}$ is a special edge. By R20, $f_1$ gets at least 1. Clearly, $f_1$ is only incident with a bad vertex $v$. This together with R22 implies that ${\omega ^*}\left(v \right) \ge - \frac{{49}}{{114}} + 1 > 0$. Next, we consider the case when $f_1$ and $f_2$ are $6^+$-faces.

Suppose that $f_3$ or $f_4$ is a 5-face. Without loss of generality, let $f_4$ be a 5-face, then $f_3$ is a $6^+$-face. After the first step, $\omega '\left(v \right) \ge 1 - \left({\frac{1}{3} + \frac{5}{\Delta }} \right) \times 3 - \left({\frac{5}{{\Delta - 1}} - \frac{1}{4}} \right) + \frac{{d\left({{f_1}} \right) - 5}}{{d\left({{f_1}} \right)}} + \frac{{d\left({{f_2}} \right) - 5}}{{d\left({{f_2}} \right)}} + \frac{{d\left({{f_3}} \right) - 5}}{{d\left({{f_3}} \right)}}$ (observe that $v_4$ is adjacent to a $(\Delta-1)^+$-vertex if $v_4$ is a $3(1)$-vertex). Since $d\left({{v'_i}} \right) = \Delta$ for $1 \le i \le 3$, $\omega '\left({{f_j}} \right) \ge \frac{{2\left({d\left({{f_j}} \right) - 5} \right)}}{{d\left({{f_j}} \right)}}$ for $1 \le j \le 2$, $\omega '\left({{f_3}} \right) \ge \frac{{d\left({{f_3}} \right) - 5}}{{d\left({{f_3}} \right)}}$. It is easy to see that $f_j$ is incident with at most $\left\lfloor {\frac{{d\left({{f_j}} \right) - 4}}{2}} \right\rfloor + 1$ bad vertices for $1 \le j \le 2$, $f_3$ is incident with at most $\left\lfloor {\frac{{d\left({{f_3}} \right) - 3}}{2}} \right\rfloor + 1$ bad vertices. Claim that $d(f_i) \ge 6$, $\frac{{d\left({{f_i}} \right) - 5}}{{d\left({{f_i}} \right)}} + \frac{{2\left({d\left({{f_i}} \right) - 5} \right)}}{{d\left({{f_i}} \right)}} \times \frac{1}{{\left\lfloor {\frac{{d\left({{f_i}} \right) - 4}}{2}} \right\rfloor + 1}} \ge \frac{1}{3}$ for $i = 1, 2$; $\frac{{d\left({{f_3}} \right) - 5}}{{d\left({{f_3}} \right)}} + \frac{{d\left({{f_3}} \right) - 5}}{{d\left({{f_3}} \right)}} \times \frac{1}{{\left\lfloor {\frac{{d\left({{f_3}} \right) - 3}}{2}} \right\rfloor + 1}} \ge \frac{1}{4}$. By R22,

Suppose $d(f_i) \ge 6$ for $1 \le i \le 4$. After the first step,

Since $d\left({{v'_i}} \right) = \Delta$ for $1 \le i \le 3$, we can get $\omega '(f_i) \ge \frac{{2\left({d\left({{f_i}} \right) - 5} \right)}}{{d\left({{f_i}} \right)}}$ for $1 \le i \le 2$, $\omega '(f_k) \ge \frac{{d\left({{f_k}} \right) - 5}}{{d\left({{f_k}} \right)}}$ for $3 \le k \le 4$. It is clear that $f_i$ is incident with at most $\left\lfloor {\frac{{d\left({{f_i}} \right) - 4}}{2}} \right\rfloor + 1$ bad vertices (i = 1, 2), $f_k$ is incident with at most $\left\lfloor {\frac{{d\left({{f_k}} \right) - 3}}{2}} \right\rfloor + 1$ bad vertices ($k$ = 3, 4). By R22,

(4) $v$ is IV-vertex, see Figure 1d. By Lemma 2.1, $d\left({{v'_i}} \right) = \Delta$ for $1 \le i \le4$.

There is exactly one 5-face in $f_1$, $f_2$, $f_3$ and $f_4$. Without loss of generality, let $f_1$ be a 5-face, then ${v'_1}{v'_2}$ is a special edge. By R20, $f_1$ gets at least 1. It is easy to see that $f_1$ is only incident with a bad vertex $v$. By R22, ${\omega ^*}\left(v \right) \ge - 1 + 1 = 0$. Next, we consider $f_i$ ($1\le i \le 4$) is $6^+$-face.

Suppose $v$ is incident with at least a 6-face. Without loss of generality, let $f_1$ be a 6-face. It is clear that $f_1$ is only incident with a bad vertex $v$. Since $d\left({{v'_1}} \right) = d\left({{v'_2}} \right) = d\left({{v'_3}} \right) = \Delta$, we can get $\omega '\left({{f_1}} \right) \ge \frac{1}{6}$. We use $m_6$ to denote the number of 6-faces which is incident with $v$. After the first step and the second step, ${\omega ^*}\left(v \right) \ge 1 - \left({\frac{1}{3} + \frac{5}{\Delta }} \right) \times 4 + \frac{1}{6} \times {m_6} + \frac{2}{7} \times \left({4 - {m_6}} \right) + \frac{2}{6} \times {m_6} = - \frac{4}{{21}} + \frac{3}{{14}}{m_6} \ge \frac{5}{{21}} > 0$.

Suppose $v$ is incident with four $7^+$-faces. Note that $f_i$ is incident with at most $\left\lfloor {\frac{{d\left({{f_i}} \right) - 4}}{2}} \right\rfloor + 1 \; (1 \le i \le 4)$ bad vertices. Since $d\left({{v'_i}} \right) = \Delta$, we can get $\omega '\left({{f_i}} \right) \ge \frac{{2\left({d\left({{f_i}} \right) - 5} \right)}}{{d\left({{f_i}} \right)}}$ ($1 \le i \le 4$). After the first step,

By R22,

Now we have checked that the final weight $w^{*}(x)\geq0$ for each $x\in V\cup F$. Then,

which is a contradiction.

3.   Conclusions

In this paper, we consider the injective chromatic index of planar graphs without adjacent 5-cycles and proved that such graphs have $\chi_i(G)\leq\Delta(G)+2$ if $g(G)\geq5$ and $\Delta \left(G \right) \ge 20$. A natural problem in context of our main result is the following: What is the optimal constant $c$ such that $\chi_i(G)\leq\Delta(G)+2$ for every planar graph G with $g(G)\geq5$ and $\Delta \left(G \right) \ge c$.

Acknowledgments

This work was supported by National Natural Science Foundations of China (Grant Nos. 11771403, 11871439, 11901243 and 12201569)

Conflict of interest

The authors declare no conflicts of interest.