The strict neighbor-distinguishing index of simple graphs with maximum degree five

Huang, Danjun; Wang, Jiayan; Wang, Weifan; Jing, Puning

doi:10.61091/ars162-13

Abstract

1. Introduction
2. Main results
Funding

References

Ars Combinatoria

Volume 162
Pages: 177-189

Research article

The strict neighbor-distinguishing index of simple graphs with maximum degree five

^¹, ^¹, ^¹, ^²

¹Department of Mathematics, Zhejiang Normal University, Jinhua 321004, China

²Department of School of Mathematical and Statistics, Xuzhou University of technology, Xuzhou 221018, China

Received: 29/04/2024
Accepted: 22/01/2025
Published Online: 29/03/2025

Copyright Link
License

Abstract

Suppose that $ϕ$ is a proper edge- $k$ -coloring of the graph $G$ . For a vertex $v \in V (G)$ , let $C_{ϕ} (v)$ denote the set of colors assigned to the edges incident with $v$ . The proper edge- $k$ -coloring $ϕ$ of $G$ is strict neighbor-distinguishing if for any adjacent vertices $u$ and $v$ , $C_{ϕ} (u) ⊊ C_{ϕ} (v)$ and $C_{ϕ} (v) ⊊ C_{ϕ} (u)$ . The strict neighbor-distinguishing index, denoted $χ_{s n d}^{'} (G)$ , is the minimum integer $k$ such that $G$ has a strict neighbor-distinguishing edge- $k$ -coloring. In this paper we prove that if $G$ is a simple graph with maximum degree five, then $χ_{s n d}^{'} (G) \leq 12$ .

Keywords: strict neighbor-distinguishing edge coloring, local neighbor-distinguishing edge coloring, maximum degree

1. Introduction

All graphs considered in this paper are finite and simple. Let $G$ be a graph with vertex set $V (G)$ and edge set $E (G)$ . For a vertex $v \in V (G)$ , let $N_{G} (v)$ be the set of neighbors of $v$ in $G$ , and $d_{G} (v)$ be the degree of $v$ in $G$ . Then, $d_{G} (v) = | N_{G} (v) |$ . Let $δ (G)$ and $Δ (G)$ (for short $Δ$ ) be the minimum and maximum degree of $G$ , respectively. The girth $g (G)$ of a graph $G$ is the length of a shortest cycle in $G$ . A $k$ -vertex, a $k^{-}$ -vertex, and a $k^{+}$ -vertex of $G$ is a vertex with degree $k$ , at most $k$ , and at least $k$ . Let $n_{k} (v)$ denote the number of $k$ -vertices adjacent to $v$ .

A proper edge- $k$ -coloring of the graph $G$ is a function $ϕ : E (G) \to {1, 2, \dots, k}$ such that any two adjacent edges receive different colors. The chromatic index $χ^{'} (G)$ of $G$ is the smallest integer $k$ such that $G$ has a proper edge- $k$ -coloring. Given a proper edge- $k$ -coloring $ϕ$ of $G$ , we use $C_{ϕ} (v)$ to denote the set of colors assigned to the edges incident with $v$ . We say that two adjacent vertices $u$ and $v$ are exclusive in $ϕ$ , if $C_{ϕ} (v) ⊊ C_{ϕ} (u)$ and $C_{ϕ} (u) ⊊ C_{ϕ} (v)$ . The proper edge- $k$ -coloring $ϕ$ is neighbor-distinguishing if $C_{ϕ} (u) \neq C_{ϕ} (v)$ for any $u v \in E (G)$ . The neighbor-distinguishing index $χ_{a}^{'} (G)$ is the smallest integer $k$ such that $G$ has a neighbor-distinguishing edge- $k$ -coloring. The proper edge- $k$ -coloring $ϕ$ is strict neighbor-distinguishing if any two adjacent vertices are exclusive. The strict neighbor-distinguishing index $χ_{s n d}^{'} (G)$ is the smallest integer $k$ such that $G$ has a strict neighbor-distinguishing edge- $k$ -coloring. The proper edge- $k$ -coloring $ϕ$ is local neighbor-distinguishing (for short, $k$ -LNDE-coloring) if any two adjacent $2^{+}$ -vertices are exclusive. The local neighbor-distinguishing index $χ_{l n d}^{'} (G)$ is the smallest integer $k$ such that $G$ has a local neighbor-distinguishing edge- $k$ -coloring.

A graph $G$ is normal if it has no isolated edges, and formal if $δ (G) \geq 2$ . The graph $G$ has a neighbor-distinguishing edge coloring iff $G$ is a normal graph and $G$ has a strict neighbor-distinguishing edge coloring iff $G$ is a formal graph. It is evident that $χ_{s n d}^{'} (G) \geq χ_{a}^{'} (G) \geq Δ$ for any formal graph $G$ . Moreover, the following propositions hold obviously.

Proposition 1.1. If

G

is a formal graph, then

χ_{l n d}^{'} (G) = χ_{s n d}^{'} (G)

Proposition 1.2. If

G

is a

r (r \geq 2)

-regular graph, then

χ_{l n d}^{'} (G) = χ_{s n d}^{'} (G) = χ_{a}^{'} (G)

Zhang et al. [11] introduced the neighbor-distinguishing edge-coloring and proposed the following conjecture.

Conjecture 1.3. For any normal graph

G

G \neq C_{5}

, then

χ_{a}^{'} (G) \leq Δ + 2

Akbari et al. 1] proved that every normal graph $G$ satisfies $χ_{a}^{'} (G) \leq 3 Δ$ . The upper bound was improved to $2.5 Δ$ by Wang et al. 10], and to $2 Δ + 2$ by Vučković 8]. In 2005, Hatami 5] showed that every normal graph $G$ with $Δ > 10^{20}$ has $χ_{a}^{'} (G) \leq Δ + 300$ . Joret and Lochet 7] improved this result to that $χ_{a}^{'} (G) \leq Δ + 19$ for any normal graph $G$ with sufficiently large $Δ$ . Huang et al. 6] showed that $χ_{a}^{'} (G) \leq Δ + 2$ for any normal planar graph $G$ with $Δ \geq 10$ . Moreover, Wang et al. 9] showed that $Δ \leq χ_{a}^{'} (G) \leq Δ + 1$ for any normal planar graph $G$ with $Δ \geq 14$ , and $χ_{a}^{'} (G) = Δ + 1$ if and only if $G$ contains adjacent $Δ$ -vertices.

The strict neighbor-distinguishing edge-coloring of graphs was studied in 12] (called the smarandachely adjacent vertex edge coloring). Gu et al. 3] found a graph $H_{n}$ $(n \geq 2)$ which is a graph obtained from the bipartite graph $K_{2, n}$ by inserting a 2-vertex into one edge. It is easy to show that $χ_{s n d}^{'} (H_{n})$ = $2 n + 1$ = $2 Δ (H_{n}) + 1$ . Based on these facts, Gu et al. 3] proposed the following conjecture.

Conjecture 1.4. If

G

is a connected formal graph, different from

H_{Δ}

, then

χ_{s n d}^{'} (G) \leq 2 Δ

Since $χ_{s n d}^{'} (K_{2, n})$ = $2 n$ = $2 Δ (K_{2, n})$ , the upper bound $2 Δ$ in Conjecture 1.4 is tight. Gu et al. 3] proved that the Conjecture 1.4 holds for the graphs with $Δ \leq 3$ . Recently, Gu et al. 4] proved that the Conjecture 1.4 holds for $K_{4}$ -minor-free graphs. Moreover, Gu 2] proved that $χ_{s n d}^{'} (G) \leq 9$ for the formal graph $G$ with $Δ \leq 4$ .

In this paper, we show that $χ_{s n d}^{'} (G) \leq 12$ for a formal graph $G$ with $Δ \leq 5$ . That is, we show the following theorem.

Theorem 1.5.

χ_{s n d}^{'} (G) \leq 12

for any formal graph

G

with

Δ \leq 5

Theorem 1.6.

χ_{l n d}^{'} (G) \leq 12

for any formal graph

G

with

Δ \leq 5

2. Main results

This section is devoted to show the main result in this paper. For an LNDE-coloring $ϕ$ , set $R (v) = {r_{i} \in C_{ϕ} (u_{i}) ∖ C_{ϕ} (v) | u_{i} v \in E (G)$ and $d_{G} (u_{i}) < d_{G} (v)}$ .

We introduce some useful lemmas.

Lemma 2.1. 10] If

G

is a normal graph with

Δ \leq 5

, then

χ_{a}^{'} (G) \leq 10

Lemma 2.2. Let

u v \in E (G)

with

d_{G} (u) = d \geq 3

. Set

N_{G} (u) = {v, u_{1}, u_{2}, \dots, u_{d - 1}}

. If

G^{'} = G - {u v}

admits a

k

-LNDE-coloring

ϕ

using the color set

C

, then

u v

can be colored with a color

a \in C ∖ (C_{ϕ} (u) \cup R (u))

such that

u

and

u_{i}

are exclusive for any

i \in {1, 2, \dots, d - 1}

Lemma 2.3. Let

u v \in E (G)

with

d_{G} (u) = d \geq 3

. Set

N_{G} (u) = {v, u_{1}, u_{2}, \dots, u_{d - 1}}

. If

G^{'} = G - {u v}

admits a

k

-LNDE-coloring

ϕ

using the color set

C

. We delete the color of

u u_{1}

and let

F (u_{1})

denote the set of forbidden colors of

u u_{1}

which makes

u_{1}

and

w

are exclusive for any

w \in N_{G} (u_{1}) ∖ {u}

. If

d_{G} (u_{1}) \geq 3

, then

| F (u_{1}) | \leq (d_{G} (u_{1}) - 1) (7 - d_{G} (u_{1}))

Proof. Let $w \in N_{G} (u_{1}) ∖ {u}$ . Since $w$ and $u_{1}$ are exclusive in $ϕ$ , there exists a color $α \in C_{ϕ} (w) ∖ C_{ϕ} (u_{1})$ . Suppose that $u u_{1}$ can be recolored with a color $x$ . Then $x \notin C_{ϕ} (u_{1}) - {ϕ (u u_{1})}$ . If $C_{ϕ} (u_{1}) - {x} \subseteq C_{ϕ} (w)$ , then $x \notin C_{ϕ} (w) - (C_{ϕ} (u_{1}) - {ϕ (u u_{1})})$ . If $C_{ϕ} (u_{1}) - {ϕ (u u_{1})} ⊈ C_{ϕ} (w)$ , then $x \neq α$ . Therefore, $| F (u_{1}) | \leq \sum_{w \in N_{G} (u_{1}) ∖ {u}} max {d_{G} (w) - (d_{G} (u_{1}) - 1), 1} + (d_{G} (u_{1}) - 1) = (d_{G} (u_{1}) - 1) (7 - d_{G} (u_{1})) .$

Now we are ready to prove Theorem 1.6. Let $G$ be a counterexample of Theorem 1.6 with minimum number of edges. Then $χ_{l n d}^{'} (G) \geq 13$ . But for each graph $G^{'}$ with $| E (G^{'}) | < | E (G) |$ and $Δ (G^{'}) \leq 5$ , we have $χ_{l n d}^{'} (G^{'}) \leq 12$ .

Assume that $δ (G) = 1$ . Let $u v \in E (G)$ with $d_{G} (u) = 1$ . By the minimality of $G$ , $G^{'} = G - {u}$ has a 12-LNDE-coloring $ϕ$ using the color set $C$ . Suppose that $d_{G} (v) = 2$ . Let $v^{'}$ be the second neighbor of $v$ other than $u$ . Then we can color $u v$ with a color $a \in C ∖ C_{ϕ} (v^{'})$ to derive a 12-LNDE-coloring of $G$ , a contradiction. Suppose that $d_{G} (v) \geq 3$ . Then we can color $u v$ with a color $b \in C ∖ (C_{ϕ} (v) \cup R (v))$ . Since $| C ∖ (C_{ϕ} (v) \cup R (v)) | \geq 12 - 4 - 4 = 4$ , we can obtain a 12-LNDE-coloring of $G$ , a contradiction. So we can assume that $δ (G) \geq 2$ in the following discussion.

To complete the proof, we have to establish a series of auxiliary claims.

Claim 1. Let

u \in V (G)

with

d_{G} (u) \leq 4

, then

n_{4^{-}} (u) = 0

Proof. Assume to the contrary that there exists a $4^{-}$ -vertex $u$ adjacent to a $4^{-}$ -vertex $v$ . Without loss of generality, assume that $d_{G} (u) \leq d_{G} (v)$ . Let $d_{G} (u) = d$ and $d_{G} (v) = t$ . Set $N_{G} (u) = {v, u_{1}, \dots, u_{d - 1}}$ and $N_{G} (v) = {u, v_{1}, \dots, v_{t - 1}}$ .

Case 1. $d = 2$ .

By the minimality of $G$ , $G^{'} = G - {u}$ has a 12-LNDE-coloring $ϕ$ using the color set $C$ .

Suppose that $t = 2$ . If $d_{G} (u_{1}) = 2$ with $N_{G} (u_{1}) = {u, x}$ , then color $u u_{1}$ with a color $a \in C ∖ (C_{ϕ} (x) \cup C_{ϕ} (v))$ and color $u v$ with a color $b \in C ∖ (C_{ϕ} (v_{1}) \cup {ϕ (u_{1} x), a})$ to derive a 12-LNDE-coloring of $G$ , a contradiction. If $d_{G} (u_{1}) \geq 3$ , then color $u u_{1}$ with a color $a \in C ∖ (C_{ϕ} (u_{1}) \cup R (u_{1}) \cup {ϕ (v v_{1})})$ and color $u v$ with a color $b \in C ∖ (C_{ϕ} (v_{1}) \cup C_{ϕ} (u_{1}) \cup {a})$ to derive a 12-LNDE-coloring of $G$ , a contradiction.

Suppose that $3 \leq t \leq 4$ . If $d_{G} (u_{1}) = 2$ with $N_{G} (u_{1}) = {u, x}$ , then color $u u_{1}$ with a color $a \in C ∖ (C_{ϕ} (x) \cup C_{ϕ} (v))$ and color $u v$ with a color $b \in C ∖ (C_{ϕ} (v) \cup R (v) \cup {ϕ (u_{1} x), a})$ to derive a 12-LNDE-coloring of $G$ , a contradiction. If $d_{G} (u_{1}) \geq 3$ , then color $u u_{1}$ with a color $a \in C ∖ (C_{ϕ} (u_{1}) \cup R (u_{1}) \cup C_{ϕ} (v))$ and color $u v$ with a color $b \in C ∖ (C_{ϕ} (v) \cup R (v) \cup C_{ϕ} (u_{1}) \cup {a})$ . Since $| C ∖ (C_{ϕ} (u_{1}) \cup R (u_{1}) \cup C_{ϕ} (v)) | \geq 12 - 4 - 4 - 3 = 1$ and $| C ∖ (C_{ϕ} (v) \cup R (v) \cup C_{ϕ} (u_{1}) \cup {a}) | \geq 12 - 3 - 3 - 4 - 1 = 1$ , we can obtain a 12-LNDE-coloring of $G$ , a contradiction.

Case 2. $d = t = 3$ .

By Case 1, $d_{G} (u_{i}) \geq 3$ and $d_{G} (v_{i}) \geq 3$ for all $i \in {1, 2}$ . By the minimality of $G$ , $G^{'} = G - {u v}$ has a 12-LNDE-coloring $ϕ$ using the color set $C$ . Suppose that $ϕ (u u_{i}) = i$ and $ϕ (v v_{i}) = a_{i}$ , $i \in {1, 2}$ . Suppose that ${a_{1}, a_{2}} = {1, 2}$ . By Lemma 2.3, $| F (v_{1}) | \leq (d_{G} (v_{1}) - 1) (7 - d_{G} (v_{1})) \leq 9$ . Note that $a_{2} \notin C_{ϕ} (v_{1})$ , $d_{G} (v_{i}) \geq d_{G} (v)$ and $d_{G} (u_{i}) \geq d_{G} (u)$ . We recolor $v v_{1}$ with a color $x \in C ∖ ({1, 2} \cup F (v_{1}))$ . If $x \in C_{ϕ} (v_{2})$ , then we color $u v$ with a color $y \in C ∖ ({1, 2} \cup C_{ϕ} (v_{2}))$ to derive a 12-LNDE-coloring of $G$ , a contradiction. If $x \notin C_{ϕ} (v_{2})$ , then we color $u v$ with a color $y \in C ∖ {1, 2, x}$ to derive a 12-LNDE-coloring of $G$ , a contradiction. Now, suppose that ${a_{1}, a_{2}} \neq {1, 2}$ . Note that $d_{G} (v_{i}) \geq d_{G} (v)$ and $d_{G} (u_{i}) \geq d_{G} (u)$ . Then $R (u) = R (v) = \emptyset$ . Then we color $u v$ with a color $y \in C ∖ (C_{ϕ} (u) \cup R (u) \cup C_{ϕ} (v)) \cup R (v)$ to derive a 12-LNDE-coloring of $G$ by Lemma 2.2, a contradiction.

Case 3. $d = 3$ and $t = 4$ .

By Case 1 and Case 2, $d_{G} (u_{i}) \geq 4$ for all $i \in {1, 2}$ and $d_{G} (v_{i}) \geq 3$ for all $j \in {1, 2, 3}$ .

Subcase 3.1. $n_{4} (u) \geq 2$ , say $d_{G} (u_{1}) = 4$ .

By the minimality of $G$ , $G^{'} = G - {u}$ has a 12-LNDE-coloring $ϕ$ using the color set $C$ . Since $| C ∖ (C_{ϕ} (u_{2}) \cup R (u_{2}) \cup C_{ϕ} (v)) | \geq 12 - 4 - 4 - 3 = 1$ , we can color $u u_{2}$ with a color $b_{1} \in C ∖ (C_{ϕ} (u_{2}) \cup R (u_{2}) \cup C_{ϕ} (v))$ . Since $| C ∖ (C_{ϕ} (u_{1}) \cup R (u_{1}) \cup C_{ϕ} (u_{2}) \cup {b_{1}}) | \geq 12 - 3 - 3 - 4 - 1 = 1$ , we can color $u u_{1}$ with a color $b_{2} \in C ∖ (C_{ϕ} (u_{1}) \cup R (u_{1}) \cup C_{ϕ} (u_{2}) \cup {b_{1}})$ . Since $| C ∖ (C_{ϕ} (v) \cup R (v) \cup C_{ϕ} (u_{1}) \cup {b_{1}, b_{2}}) | \geq 12 - 3 - 3 - 3 - 2 = 1$ , we can color $u v$ with a color $b_{3} \in C ∖ (C_{ϕ} (v) \cup R (v) \cup C_{ϕ} (u_{1}) \cup {b_{1}, b_{2}})$ . It is easy to check that the obtained coloring is a 12-LNDE-coloring of $G$ , a contradiction.

Subcase 3.2. $n_{4} (u) \leq 1$ .

Then $d_{G} (u_{1}) = d_{G} (u_{2}) = 5$ . By the minimality of $G$ , $G^{'} = G - {u v}$ has a 12-LNDE-coloring $ϕ$ using the color set $C$ . First, suppose that $C_{ϕ} (u) \subseteq C_{ϕ} (v)$ . By Lemma 2.3, $| F (u_{1}) | \leq (d_{G} (u_{1}) - 1) (7 - d_{G} (u_{1})) = 8$ . We recolor $u u_{1}$ with a color $x \in C ∖ (C_{ϕ} (v) \cup F (u_{1}))$ . Note that $ϕ (u u_{2}) \notin C_{ϕ} (u_{1})$ . If $x \in C_{ϕ} (u_{2})$ , we can color $u v$ with a color $y \in C ∖ (C_{ϕ} (v) \cup R (v) \cup C_{ϕ} (u_{2}))$ to derive a 12-LNDE-coloring of $G$ , a contradiction. If $x \notin C_{ϕ} (u_{2})$ , then we can color $u v$ with a color $y \in C ∖ (C_{ϕ} (v) \cup R (v) \cup {x})$ to derive a 12-LNDE-coloring of $G$ , a contradiction. Then suppose that $C_{ϕ} (u) ⊊ C_{ϕ} (v)$ . Note that $R (u) = \emptyset$ . By Lemma 2.2, we can color $u v$ with a color $b \in C ∖ (C_{ϕ} (u) \cup R (u) \cup C_{ϕ} (v) \cup R (v))$ to derive a 12-LNDE-coloring of $G$ , a contradiction.

Case 4. $d = t = 4$ .

By Case 1-3, $d_{G} (u_{i}) \geq 4$ and $d_{G} (v_{i}) \geq 4$ for all $i \in {1, 2, 3}$ .

Subcase 4.1. $n_{4} (u) = 4$ .

By Case 1-3, every vertex in $N_{G} (u_{i})$ for $i \in {1, 2, 3}$ is a $4^{+}$ -vertex. By the minimality of $G$ , $G^{'} = G - {u}$ has a 12-LNDE-coloring $ϕ$ using the color set $C$ . Note that $R (u_{i}) = \emptyset$ for each $i \in {1, 2, 3}$ and $R (v) = \emptyset$ . We can color $u u_{1}$ with a color $b_{1} \in C ∖ (C_{ϕ} (u_{1}) \cup R (u_{1}) \cup C_{ϕ} (u_{2}))$ , $u u_{2}$ with a color $b_{2} \in C ∖ (C_{ϕ} (u_{2}) \cup R (u_{2}) \cup C_{ϕ} (u_{3}) \cup {b_{1}})$ , $u u_{3}$ with a color $b_{3} \in C ∖ (C_{ϕ} (u_{3}) \cup R (u_{3}) \cup C_{ϕ} (v) \cup {b_{1}, b_{2}})$ , and $u v$ with a color $b_{4} \in C ∖ (C_{ϕ} (v) \cup R (v) \cup C_{ϕ} (u_{1}) \cup {b_{1}, b_{2}, b_{3}})$ to derive a 12-LNDE-coloring of $G$ , a contradiction.

Subcase 4.2. $n_{4} (u) \leq 3$ .

Without loss of generality, suppose that $d_{G} (u_{1}) = 5$ . By the minimality of $G$ , $G^{'} = G - {u v}$ has a 12-LNDE-coloring $ϕ$ using the color set $C$ . First, suppose that $C_{ϕ} (u) = C_{ϕ} (v)$ . By Lemma 2.3, $| F (u_{1}) | \leq (d_{G} (u_{1}) - 1) (7 - d_{G} (u_{1})) = 8$ . We recolor $u u_{1}$ with a color $x \in C ∖ (C_{ϕ} (v) \cup F (u_{1}))$ . Set $C (u) = (C_{ϕ} (u) \cup {x}) ∖ {ϕ (u u_{1})}$ . If $C (u) \subseteq C_{ϕ} (u_{i})$ , then let $\bar{R} (u_{i}) = C_{ϕ} (u_{i}) ∖ C (u)$ ; otherwise, let $\bar{R} (u_{i}) = \emptyset$ . then $C (u) \subseteq C_{ϕ} (u_{i})$ , so $| \bar{R} (u_{i}) | \leq 2$ . Then we color $u v$ with a color $y \in C ∖ (C_{ϕ} (v) \cup R (v) \cup \bar{R} (u_{2}) \cup \bar{R} (u_{3}) \cup {x})$ to get a 12-LNDE-coloring of $G$ , a contradiction. Now, suppose that $C_{ϕ} (u) \neq C_{ϕ} (v)$ . Then $R (u) = \emptyset$ and $R (v) = \emptyset$ . By Lemma 2.2, we can color $u v$ with a color $y \in C ∖ (C_{ϕ} (u) \cup R (u) \cup C_{ϕ} (v) \cup R (v))$ to derive a 12-LNDE-coloring of $G$ , a contradiction.

Claim 2.

G

does not contain a

5

-cycle

C_{5} = v_{1} v_{2} v_{3} v_{4} v_{5} v_{1}

with

d_{G} (v_{1}) = d_{G} (v_{3}) = d_{G} (v_{5}) = 5

and

d_{G} (v_{2}) = d_{G} (v_{4}) = 2

Proof. Assume to the contrary that such a $5$ -cycle $C_{5}$ exists. Let $u_{1}, u_{2}, u_{3}$ be the neighbor of $v_{3}$ other than $v_{2}, v_{4}$ .

Case 1. $n_{5} (v_{3}) \geq 2$ .

By the minimality of $G$ , $G^{'} = G - {v_{2}, v_{4}}$ has a 12-LNDE-coloring $ϕ$ using the color set $C$ . Then $| R (v_{3}) | \leq 1$ . We can color $v_{1} v_{2}$ with a color $a \in C ∖ (C_{ϕ} (v_{1}) \cup R (v_{1}) \cup C_{ϕ} (v_{3}))$ , color $v_{4} v_{5}$ with a color $b \in C ∖ (C_{ϕ} (v_{5}) \cup R (v_{5}) \cup C_{ϕ} (v_{3}))$ , color $v_{2} v_{3}$ with a color $c \in C ∖ (C_{ϕ} (v_{3}) \cup R (v_{3}) \cup C_{ϕ} (v_{1}) \cup {a, b})$ , and color $v_{3} v_{4}$ with a color $d \in C ∖ (C_{ϕ} (v_{3}) \cup R (v_{3}) \cup C_{ϕ} (v_{5}) \cup {a, b, c})$ to derive a 12-LNDE-coloring of $G$ , a contradiction.

Case 2. $n_{5} (v_{3}) = 1$ , say $d_{G} (u_{3}) = 5$ .

By the minimality of $G$ , $G^{'} = G - {v_{2}, v_{4}}$ has a 12-LNDE-coloring $ϕ$ using the color set $C$ . Let $ϕ (v_{3} u_{i}) = i$ ( $i \in {1, 2, 3}$ ), $a \in C_{ϕ} (u_{1}) ∖ C_{ϕ} (v_{3})$ and $b \in C_{ϕ} (u_{2}) ∖ C_{ϕ} (v_{3})$ . Without loss of generality, assume that $a = 4$ and $b = 5$ . Note that $v_{1}$ and $v_{5}$ are exclusive in $G^{'}$ , $| R (v_{1}) | \leq 3$ and $| R (v_{5}) | \leq 3$ . Let $i \in C_{ϕ} (v_{1}) ∖ C_{ϕ} (v_{5})$ and $j \in C_{ϕ} (v_{5}) ∖ C_{ϕ} (v_{1})$ .

Subcase 2.1. $i, j \notin {1, 2, \dots, 5}$ .

We can color $v_{2} v_{3}$ with $j$ , color $v_{3} v_{4}$ with $i$ , color $v_{1} v_{2}$ with a color $c \in C ∖ (C_{ϕ} (v_{1}) \cup R (v_{1}) \cup {1, 2, 3, j})$ , and color $v_{4} v_{5}$ with a color $d \in C ∖ (C_{ϕ} (v_{5}) \cup R (v_{5}) \cup {1, 2, 3, i})$ to derive a 12-LNDE-coloring of $G$ , a contradiction.

Subcase 2.2. $i \in {1, 2, \dots, 5}$ and $j \notin {1, 2, \dots, 5}$ .

We color $v_{2} v_{3}$ with $j$ , color $v_{1} v_{2}$ with a color $a_{1} \in C ∖ (C_{ϕ} (v_{1}) \cup R (v_{1}) \cup {1, 2, 3, j})$ , color $v_{4} v_{5}$ with a color $a_{2} \in C ∖ (C_{ϕ} (v_{5}) \cup R (v_{5}) \cup {1, 2, 3, i})$ , and color $v_{3} v_{4}$ with a color $a_{3} \in C ∖ (C_{ϕ} (v_{5}) \cup {1, 2, 3, 4, 5, a_{1}, a_{2}})$ to derive a 12-LNDE-coloring of $G$ , a contradiction.

Subcase 2.3. $i, j \in {1, 2, \dots, 5}$ .

Note that $i \in C_{ϕ} (v_{1}) \cap {1, 2, \dots, 5}$ . We color $v_{1} v_{2}$ with a color $a_{1} \in C ∖ (C_{ϕ} (v_{1}) \cup R (v_{1}) \cup {1, 2, 3, j})$ , color $v_{4} v_{5}$ with a color $a_{2} \in C ∖ (C_{ϕ} (v_{5}) \cup R (v_{5}) \cup {1, 2, 3, i})$ , color $v_{3} v_{4}$ with a color $a_{3} \in C ∖ (C_{ϕ} (v_{5}) \cup {1, 2, 3, 4, 5, a_{1}, a_{2}})$ , and color $v_{2} v_{3}$ with a color $a_{4} \in C ∖ (C_{ϕ} (v_{1}) \cup {1, 2, 3, 4, 5, a_{1}, a_{2}, a_{3}})$ to derive a 12-LNDE-coloring of $G$ , a contradiction.

Case 3. $n_{5} (v_{3}) = 0$ .

Then $2 \leq d_{G} (u_{i}) \leq 4$ for every $i \in {1, 2, 3}$ . By Claim 1, all the neighbors of $u_{i}$ are $5$ -vertices. Let $C_{ϕ}^{*} (u_{i}) = C_{ϕ} (u_{i})$ when $d_{G} (u_{i}) = 3$ , and $C_{ϕ}^{*} (u_{i}) = \emptyset$ , when $d_{G} (u_{i}) = 4$ , where $i \in {1, 2, 3}$ .

Subcase 3.1. $n_{2} (v_{3}) = 2$ .

Then $3 \leq d_{G} (u_{i}) \leq 4$ for each $i \in {1, 2, 3}$ . By the minimality of $G$ , $G^{'} = G - {v_{2}, v_{3}, v_{4}}$ has a 12-LNDE-coloring $ϕ$ using color set $C$ . Hence $R (u_{i}) = \emptyset$ . We color $v_{3} v_{4}$ with a color $i \in C ∖ (C_{ϕ}^{*} (u_{1}) \cup C_{ϕ}^{*} (u_{2}) \cup C_{ϕ}^{*} (u_{3}) \cup C_{ϕ} (v_{5}))$ and color $v_{2} v_{3}$ with a color $j \in C ∖ (C_{ϕ} (v_{1}) \cup {i})$ . Note that $i \notin C_{ϕ} (u_{i})$ when $d_{G} (u_{i}) = 3$ . So there exist a color $a_{i} \in C_{ϕ} (u_{i}) ∖ {i, j}$ for any $i \in {1, 2, 3}$ . Then we color $v_{1} v_{2}$ with a color $a \in C ∖ (C_{ϕ} (v_{1}) \cup R (v_{1}) \cup {i, j})$ , color $v_{4} v_{5}$ with a color $b \in C ∖ (C_{ϕ} (v_{5}) \cup R (v_{5}) \cup {i, j})$ , color $v_{3} u_{1}$ with a color $c_{1} \in C ∖ (C_{ϕ} (u_{1}) \cup R (u_{1}) \cup {a_{2}, a_{3}, a, b, i, j})$ , color $v_{3} u_{2}$ with a color $c_{2} \in C ∖ (C_{ϕ} (u_{2}) \cup R (u_{2}) \cup {a_{1}, a_{3}, a, b, i, j, c_{1}})$ , and color $v_{3} u_{3}$ with a color $c_{3} \in C ∖ (C_{ϕ} (u_{3}) \cup R (u_{3}) \cup {a_{1}, a_{2}, a, b, i, j, c_{1}, c_{2}})$ to derive a 12-LNDE-coloring of $G$ , a contradiction.

Subcase 3.2. $n_{2} (v_{3}) = 3$ , say $d_{G} (u_{1}) = 2$ .

Let $u_{1}^{'}$ be the second neighbor of $u_{1}$ other than $v_{3}$ . Suppose that $G^{'}$ = $G - {v_{2}, v_{3}, v_{4}, u_{1}}$ . By the minimality of $G$ , $G^{'}$ has a 12-LNDE-coloring $ϕ$ using the color set $C$ . Then $R (u_{2}) = R (u_{3}) = \emptyset$ by Claim 1. We color $v_{2} v_{3}$ with a color $i \in C ∖ (C_{ϕ}^{*} (u_{2}) \cup C_{ϕ}^{*} (u_{3}) \cup C_{ϕ} (v_{1}))$ and color $v_{3} v_{4}$ with a color $j \in C ∖ (C_{ϕ} (v_{5}) \cup {i})$ . Note that $i \notin C_{ϕ} (u_{i})$ when $d_{G} (u_{i}) = 3$ for each $i \in {2, 3}$ . So there exists a color $a_{i} \in C_{ϕ} (u_{i}) ∖ {i, j}$ . Color $v_{1} v_{2}$ with a color $a \in C ∖ (C_{ϕ} (v_{1}) \cup R (v_{1}) \cup {i, j})$ , color $v_{4} v_{5}$ with a color $b \in C ∖ (C_{ϕ} (v_{5}) \cup R (v_{5}) \cup {i, j})$ , color $u_{1} u_{1}^{'}$ with a color $c \in C ∖ (C_{ϕ} (u_{1}^{'}) \cup R (u_{1}^{'}) \cup {i, j})$ , color $v_{3} u_{1}$ with a color $c_{1} \in C ∖ (C_{ϕ} (u_{1}^{'}) \cup {a_{2}, a_{3}, c, a, b, i, j})$ , color $v_{3} u_{2}$ with a color $c_{2} \in C ∖ (C_{ϕ} (u_{2}) \cup R (u_{2}) \cup {a_{3}, c, a, b, i, j, c_{1}})$ , and color $v_{3} u_{3}$ with a color $c_{3} \in C ∖ (C_{ϕ} (u_{3}) \cup R (u_{3}) \cup {a_{2}, c, a, b, i, j, c_{1}, c_{2}})$ to derive a 12-LNDE-coloring of $G$ , a contradiction.

Subcase 3.3. $n_{2} (v_{3}) = 4$ , say $d_{G} (u_{1}) = d_{G} (u_{2}) = 2$ .

Let $u_{i}^{'}$ be the second neighbor of $u_{i}$ other than $v_{3}$ for each $i \in {1, 2}$ . Let $G^{'} = G - {v_{2}, v_{3}, v_{4}, u_{1}, u_{2}}$ . By the minimality of $G$ , $G^{'}$ has a 12-LNDE-coloring $ϕ$ using the color set $C$ . Since $v_{1} v_{5} \in E (G^{'})$ , there exists a color $i \in C_{ϕ} (v_{1}) ∖ C_{ϕ} (v_{5})$ and $j \in C_{ϕ} (v_{5}) ∖ C_{ϕ} (v_{1})$ . Note that $| R (v_{1}) | \leq 3$ and $| R (v_{5}) | \leq 3$ . Color $v_{2} v_{3}$ with a color $j$ and color $v_{3} v_{4}$ with a color $i$ .

Suppose that $d_{G} (u_{3}) = 4$ . Then there exists a color $x \in C_{ϕ} (u_{3}) ∖ {i, j}$ , say $x = 1$ . Note that $R (u_{3}) = \emptyset$ by Claim 1. We color $u_{1} u_{1}^{'}$ with a color $a_{1} \in C ∖ (C_{ϕ} (u_{1}^{'})) \cup R (u_{1}^{'}) \cup {i, j}$ , color $u_{2} u_{2}^{'}$ with a color $a_{2} \in C ∖ (C_{ϕ} (u_{2}^{'}) \cup R (u_{2}^{'}) \cup {i, j})$ , color $v_{3} u_{1}$ with a color $b_{1} \in C ∖ (C_{ϕ} (u_{1}^{'}) \cup {a_{1}, a_{2}, 1, i, j})$ , color $v_{3} u_{2}$ with a color $b_{2} \in C ∖ (C_{ϕ} (u_{2}^{'}) \cup {a_{1}, a_{2}, 1, i, j, b_{1}})$ , color $v_{3} u_{3}$ with a color $b_{3} \in C ∖ (C_{ϕ} (u_{3}) \cup R (u_{3}) \cup {a_{1}, a_{2}, i, j, b_{1}, b_{2}})$ , color $v_{1} v_{2}$ with a color $a \in C ∖ (C_{ϕ} (v_{1}) \cup R (v_{1}) \cup {b_{1}, b_{2}, b_{3}, j})$ , and color $v_{4} v_{5}$ with a color $b \in C ∖ (C_{ϕ} (v_{5}) \cup R (v_{5}) \cup {b_{1}, b_{2}, b_{3}, i})$ to derive a 12-LNDE-coloring of $G$ , a contradiction.

Suppose that $d_{G} (u_{3}) = 3$ . Let $u_{3}^{'}$ , $u_{3}^{″}$ be the neighbors of $u_{3}$ other than $v_{3}$ . Let $ϕ (u_{3} u_{3}^{'}) = 1$ and $ϕ (u_{3} u_{3}^{″}) = 2$ . First assume that ${1, 2} \neq {i, j}$ , say $1 \notin {i, j}$ . With the same coloring as $d_{G} (u_{3}) = 4$ , we can obtain a 12-LNDE-coloring of $G$ , a contradiction. So assume that ${1, 2} = {i, j}$ . By Lemma 2.3, $| F (u_{3}^{'}) | \leq (d_{G} (u_{3}^{'}) - 1) (7 - d_{G} (u_{3}^{'})) = 8$ . Note that $2 \notin C_{ϕ} (u_{3}^{'})$ . We recolor $u_{3} u_{3}^{'}$ with a color $x \in C ∖ (F (u_{3}^{'}) \cup {i, j})$ , color $u_{1} u_{1}^{'}$ with a color $a_{1} \in C ∖ (C_{ϕ} (u_{1}^{'}) \cup R (u_{1}^{'}) \cup {i, j})$ , color $u_{2} u_{2}^{'}$ with a color $a_{2} \in C ∖ (C_{ϕ} (u_{2}^{'}) \cup R (u_{2}^{'}) \cup {i, j})$ , color $v_{3} u_{3}$ with a color $b_{3} \in C ∖ (C_{ϕ} (u_{3}^{″}) \cup {i, j, x, a_{1}, a_{2}})$ , color $v_{3} u_{1}$ with a color $b_{1} \in C ∖ (C_{ϕ} (u_{1}^{'}) \cup {a_{1}, a_{2}, x, i, j, b_{3}})$ , color $v_{3} u_{2}$ with a color $b_{2} \in C ∖ (C_{ϕ} (u_{2}^{'}) \cup {a_{1}, a_{2}, x, i, j, b_{1}, b_{3}})$ , color $v_{1} v_{2}$ with a color $a \in C ∖ (C_{ϕ} (v_{1}) \cup R (v_{1}) \cup {b_{1}, b_{2}, b_{3}, j})$ , and color $v_{4} v_{5}$ with a color $b \in C ∖ (C_{ϕ} (v_{5}) \cup R (v_{5}) \cup {b_{1}, b_{2}, b_{3}, i})$ to derive a 12-LNDE-coloring of $G$ , a contradiction.

Subcase 3.4. $n_{2} (v_{3}) = 5$ , say $d_{G} (u_{1}) = d_{G} (u_{2}) = d_{G} (u_{3}) = 2$ .

Let $u_{i}^{'}$ be the neighbors of $u_{i}$ other than $u$ for each $i \in {1, 2, 3}$ . Let $G^{'}$ = $G - {v_{2}, v_{3}, v_{4}, u_{1},$ $u_{2}, u_{3}}$ . By the minimality of $G$ , $G^{'}$ has a 12-LNDE-coloring $ϕ$ using the color set $C$ . Since $v_{1} v_{5} \in E (G^{'})$ , there exists a color $i \in C_{ϕ} (v_{1}) ∖ C_{ϕ} (v_{5})$ and $j \in C_{ϕ} (v_{5}) ∖ C_{ϕ} (v_{1})$ . Note that $| R (v_{1}) | \leq 3$ and $| R (v_{5}) | \leq 3$ . We color $v_{2} v_{3}$ with $j$ , color $v_{3} v_{4}$ with $i$ , color $u_{i} u_{i}^{'}$ with a color $a_{i} \in C ∖ (C_{ϕ} (u_{i}^{'}) \cup R (u_{i}^{'}) \cup {i, j})$ for each $i \in {1, 2, 3}$ , color $v_{3} u_{1}$ with a color $b_{1} \in C ∖ (C_{ϕ} (u_{1}^{'}) \cup {a_{1}, a_{2}, a_{3}, i, j})$ , color $v_{3} u_{2}$ with a color $b_{2} \in C ∖ (C_{ϕ} (u_{2}^{'}) \cup {a_{1}, a_{2}, a_{3}, i, j, b_{1}})$ , color $v_{3} u_{3}$ with a color $b_{3} \in C ∖ (C_{ϕ} (u_{3}^{'}) \cup {a_{1}, a_{2}, a_{3}, i, j, b_{1}, b_{2}})$ , color $v_{1} v_{2}$ with a color $a \in C ∖ (C_{ϕ} (v_{1}) \cup R (v_{1}) \cup {b_{1}, b_{2}, b_{3}, j})$ , and color $v_{4} v_{5}$ with a color $b \in C ∖ (C_{ϕ} (v_{5}) \cup R (v_{5}) \cup {b_{1}, b_{2}, b_{3}, i})$ to derive a 12-LNDE-coloring of $G$ , a contradiction.

Claim 3.

G

does not contain a path

P_{3} = u v w

such that

d_{G} (u) = 3

d_{G} (v) = 5

and

3 \leq d_{G} (w) \leq 4

Proof. Assume to the contrary that such a path $P_{3} = u v w$ exists. By Claim 1, $u w \notin E (G)$ . Suppose that $d_{G} (w) = k$ . Let $u_{1}, u_{2}$ be the neighbors of $u$ not in $P_{3}$ , $w_{1}, \dots, w_{k - 1}$ be the neighbors of $w$ not in $P_{3}$ , and $v_{1}, v_{2}, v_{3}$ be the neighbors of $v$ not in $P_{3}$ .

Case 1. $n_{5} (v) = 0$ .

By the minimality of $G$ , $G^{'} = G - v$ has a 12-LNDE-coloring $ϕ$ using the color set $C$ . Let $a_{1} \in C_{ϕ} (u)$ , $a_{2} \in C_{ϕ} (w)$ , $a_{i + 2} \in C_{ϕ} (v_{i})$ , where $i \in {1, 2, 3}$ . By Claim 1, $R (u) = \emptyset$ and $R (w) = \emptyset$ . Moreover, if $3 \leq d_{G} (v_{i}) \leq 4$ , $R (v_{i}) = \emptyset$ by Claim 1. For each $i \in {1, 2, 3}$ , let $F^{*} (v_{i}) = C_{ϕ} (v_{i}^{'})$ when $d_{G} (v_{i}) = 2$ with the second neighbor $v_{i}^{'}$ other than $v$ , and $F^{*} (v_{i}) = C_{ϕ} (v_{i}) \cup R (v_{i}) = C_{ϕ} (v_{i})$ when $3 \leq d_{G} (v_{i}) \leq 4$ . Then we can color $v v_{i}$ with a color in $C ∖ F^{*} (v_{i})$ such that $v_{i}$ and its neighbors are exclusive. We color $v v_{1}$ with a color $b_{1} \in C ∖ (F^{*} (v_{1}) \cup {a_{1}, a_{2}, a_{4}, a_{5}})$ , color $v v_{2}$ with a color $b_{2} \in C ∖ (F^{*} (v_{2}) \cup {a_{1}, a_{2}, a_{3}, a_{5}, b_{1}})$ , color $v v_{3}$ with a color $b_{3} \in C ∖ (F^{*} (v_{3}) \cup {a_{1}, a_{2}, a_{3}, a_{4}, b_{1}, b_{2}})$ , color $u v$ with a color $b_{4} \in C ∖ (C_{ϕ} (u) \cup R (u) \cup {a_{2}, a_{3}, a_{4}, a_{5}, b_{1}, b_{2}, b_{3}})$ , and color $w v$ with a color $b_{5} \in C ∖ (C_{ϕ} (w) \cup R (w) \cup {a_{1}, a_{3}, a_{4}, a_{5}, b_{1}, b_{2}, b_{3}, b_{4}})$ to derive a 12-LNDE-coloring of $G$ , a contradiction.

Case 2. $n_{5} (v) \geq 1$ .

By the minimality of $G$ , $G^{'} = G - {u v, v w}$ has a 12-LNDE-coloring $ϕ$ using the color set $C$ . Then $| R (v) | \leq 2$ . Without loss of generality, suppose that $ϕ (v v_{j}) = j$ for $j \in {1, 2, 3}$ , $ϕ (u u_{i}) = a_{i}$ for $i \in {1, 2}$ , and $ϕ (w w_{l}) = b_{l}$ for $l \in {1, \dots, k - 1}$ .

Subcase 2.1. $C_{ϕ} (u) \subseteq C_{ϕ} (v)$ , $C_{ϕ} (w) \subseteq C_{ϕ} (v)$ .

Suppose that $d_{G} (w) = 3$ . By Lemma 2.3, $| F (u_{1}) | \leq (d_{G} (u_{1}) - 1) (7 - d_{G} (u_{1})) = (5 - 1) (7 - 5) = 8$ and $| F (w_{1}) | \leq 8$ . We recolor $u u_{1}$ with a color $x \in C ∖ (F (u_{1}) \cup C_{ϕ} (v))$ , recolor $w w_{1}$ with a color $y \in C ∖ (F (w_{1}) \cup C_{ϕ} (v))$ . Note that $a_{2} \notin C_{ϕ} (u_{1})$ . So $u$ and $u_{1}$ are exclusive. Similarly, $w$ and $w_{1}$ are exclusive. If $x \notin C_{ϕ} (u_{2})$ , then we color $u v$ with a color $c_{1} \in C ∖ (C_{ϕ} (v) \cup R (v) \cup {x, y})$ ; otherwise, we color $u v$ with a color $c_{1} \in C ∖ (C_{ϕ} (v) \cup R (v) \cup C_{ϕ} (u_{2}) \cup {y})$ . If $y \notin C_{ϕ} (w_{2})$ , then we color $w v$ with a color $c_{2} \in C ∖ (C_{ϕ} (v) \cup R (v) \cup {x, y, c_{1}})$ ; otherwise, we color $w v$ with a color $c_{2} \in C ∖ (C_{ϕ} (v) \cup R (v) \cup C_{ϕ} (w_{2}) \cup {x, c_{1}})$ . Note that $b_{2} \in C_{ϕ} (w_{2}) \cap C_{ϕ} (w) \subseteq C_{ϕ} (v)$ . Then $| C ∖ (C_{ϕ} (v) \cup R (v) \cup C_{ϕ} (w_{2}) \cup {x, c_{1}}) | \geq 12 - 3 - 2 - 5 - 2 + 1 = 1$ . Hence, the obtained coloring is the 12-LNDE-coloring of $G$ , a contradiction.

Suppose that $d_{G} (w) = 4$ . By Lemma 2.3. $| F (u_{1}) | \leq (d_{G} (u_{1}) - 1) (7 - d_{G} (u_{1})) = 8$ and $| F (w_{1}) | \leq 8$ . We recolor $u u_{1}$ with a color $x \in C ∖ (F (u_{1}) \cup C_{ϕ} (v))$ and recolor $w w_{1}$ with a color $y \in C ∖ (F (w_{1}) \cup C_{ϕ} (v))$ . For $i \in {2, 3}$ , if ${y, b_{2}, b_{3}} \subseteq C_{ϕ} (w_{i})$ , let $\bar{R} (w_{i}) = C_{ϕ} (w_{i}) ∖ {y, b_{2}, b_{3}}$ ; otherwise, let $\bar{R} (w_{i}) = \emptyset$ . Note that $C_{ϕ} (w) = C_{ϕ} (v)$ . We color $w v$ with a color $c_{1} \in C ∖ (C_{ϕ} (v) \cup R (v) \cup \bar{R} (w_{2}) \cup \bar{R} (w_{3}) \cup {x, y})$ . If $x \notin C_{ϕ} (u_{2})$ , we color $u v$ with a color $c_{2} \in C ∖ (C_{ϕ} (v) \cup R (v) \cup {x, c_{1}, y})$ ; otherwise, we color $u v$ with a color $c_{2} \in C ∖ (C_{ϕ} (v) \cup R (v) \cup C_{ϕ} (u_{2}) \cup {c_{1}, y})$ . Note that $a_{2} \in C_{ϕ} (u_{2}) \cap C_{ϕ} (u) \subseteq C_{ϕ} (v)$ . Then $| C ∖ (C_{ϕ} (v) \cup R (v) \cup C_{ϕ} (u_{2}) \cup {c_{1}, y}) | \geq 12 - 3 - 2 - 5 - 2 + 1 = 1$ . Hence, the obtained coloring is the 12-LNDE-coloring of $G$ , a contradiction.

Subcase 2.2. $C_{ϕ} (u) \subseteq C_{ϕ} (v)$ , $C_{ϕ} (w) ⊊ C_{ϕ} (v)$ .

Let $α \in C_{ϕ} (w) ∖ C_{ϕ} (v)$ . By Lemma 2.3, $| F (u_{1}) | \leq 8$ . We recolor $u u_{1}$ with a color $x \in C ∖ (F (u_{1}) \cup C_{ϕ} (v))$ . If $x \notin C_{ϕ} (u_{2})$ , then we color $u v$ with a color $c_{1} \in C ∖ (C_{ϕ} (v) \cup R (v) \cup {x, α})$ ; otherwise, we color $u v$ with a color $c_{1} \in C ∖ (C_{ϕ} (v) \cup R (v) \cup C_{ϕ} (u_{2}) \cup {α})$ . Then we color $w v$ with a color $c_{2} \in C ∖ (C_{ϕ} (v) \cup R (v) \cup C_{ϕ} (w) \cup {x, c_{1}})$ to derive a 12-LNDE-coloring of $G$ , a contradiction.

Subcase 2.3. $C_{ϕ} (u) ⊊ C_{ϕ} (v)$ , $C_{ϕ} (w) \subseteq C_{ϕ} (v)$ .

If $d_{G} (w) = 3$ , then the proof is the same as Subcase 2.2. So suppose that $d_{G} (w) = 4$ . Let $α \in C_{ϕ} (u) ∖ C_{ϕ} (v)$ . By Lemma 2.3, $| F (w_{1}) | \leq 8$ . We recolor $w w_{1}$ with a color $y \in C ∖ (F (w_{1}) \cup C_{ϕ} (v))$ . For $i \in {2, 3}$ , if ${y, b_{2}, b_{3}} \subseteq C_{ϕ} (w_{i})$ , then let $\bar{R} (w_{i}) = C_{ϕ} (w_{i}) ∖ {y, b_{2}, b_{3}}$ , otherwise, let $\bar{R} (w_{i}) = \emptyset$ . Note that $C_{ϕ} (w) = C_{ϕ} (v)$ . We color $w v$ with a color $c_{1} \in C ∖ (C_{ϕ} (v) \cup R (v) \cup \bar{R} (w_{2}) \cup \bar{R} (w_{3}) \cup {α, y})$ , and color $u v$ with a color $c_{2} \in C ∖ (C_{ϕ} (u) \cup C_{ϕ} (v) \cup R (v) \cup {c_{1}, y})$ to derive a 12-LNDE-coloring of $G$ , a contradiction.

Subcase 2.4. $C_{ϕ} (u) ⊊ C_{ϕ} (v)$ , $C_{ϕ} (w) ⊊ C_{ϕ} (v)$ .

Let $α \in C_{ϕ} (u) ∖ C_{ϕ} (v)$ and $β \in C_{ϕ} (w) ∖ C_{ϕ} (v)$ . We color $u v$ with a color $c_{1} \in C ∖ (C_{ϕ} (v) \cup R (v) \cup C_{ϕ} (u) \cup {β})$ , and color $w v$ with a color $c_{2} \in C ∖ (C_{ϕ} (v) \cup R (v) \cup C_{ϕ} (w) \cup {α, c_{1}})$ to derive a 12-LNDE-coloring of $G$ , a contradiction.

Claim 4.

G

does not contain a path

P_{3} = u v w

such that

d_{G} (u) = 4

d_{G} (v) = 5

and

d_{G} (w) = 4

Proof. Assume to the contrary that such a path $P_{3} = u v w$ exists. By Claim 1, $u w \notin E (G)$ . Let $u_{1}, u_{2}, u_{3}$ be the neighbors of $u$ not in $P_{3}$ , $w_{1}, w_{2}, w_{3}$ be the neighbors of $w$ not in $P_{3}$ , and $v_{1}, v_{2}, v_{3}$ be the neighbors of $v$ not in $P_{3}$ . By Claim 1, $R (u) = R (w) = \emptyset$ . If $n_{5} (v) = 0$ , then the proof is the same as Case 1 of Claim 3. So suppose that $n_{5} (v) \geq 1$ , say $d_{G} (v_{1}) = 5$ . Then, $| R (v) | \leq 2$ . By Lemma 2.3, $| F (v_{1}) | \leq 8$ . By the minimality of $G$ , $G^{'} = G - {u v, v w}$ has a 12-LNDE-coloring $ϕ$ using the color set $C$ .

Case 1. $C_{ϕ} (u) = C_{ϕ} (v) = C_{ϕ} (w)$ .

Suppose that $n_{2} (v) = 0$ . By Claim 3, $d_{G} (v_{2}) = d_{G} (v_{3}) \geq 4$ . Note that $v$ and $v_{1}$ are exclusive in $G^{'}$ . We recolor $v v_{1}$ with a color $x \in C ∖ (F (v_{1}) \cup C_{ϕ} (v))$ . Then there exists a color $a_{i} \in C_{ϕ} (v_{i}) ∖ ((C_{ϕ} (v) - {ϕ (v v_{1})}) \cup {x})$ for each $i \in {2, 3}$ . Color $u v$ with a color $b_{1} \in C ∖ (C_{ϕ} (u) \cup R (u) \cup {x, a_{2}, a_{3}})$ , and color $w v$ with a color $b_{2} \in C ∖ (C_{ϕ} (w) \cup R (w) \cup {x, b_{1}, a_{2}, a_{3}})$ to derive a 12-LNDE-coloring of $G$ , a contradiction.

Suppose that $n_{2} (v) = 1$ , say $d_{G} (v_{2}) = 2$ . Let $v_{2}^{'}$ be the second neighbor of $v_{2}$ other than $v$ . By Claim 3, $d_{G} (v_{3}) \geq 4$ . We recolor $v v_{2}$ with a color $x \in C ∖ (C_{ϕ} (v_{2}^{'}) \cup C_{ϕ} (v))$ . Then there exists a color $a_{i} \in C_{ϕ} (v_{i}) ∖ ((C_{ϕ} (v) - {ϕ (v v_{2})}) \cup {x})$ for each $i \in {1, 3}$ . We color $u v$ with a color $b_{1} \in C ∖ (C_{ϕ} (u) \cup R (u) \cup C_{ϕ} (v_{2}) \cup {x, a_{1}, a_{3}})$ , and color $w v$ with a color $b_{2} \in C ∖ (C_{ϕ} (w) \cup R (w) \cup C_{ϕ} (v_{2}) \cup {b_{1}, x, a_{1}, a_{3}})$ to derive a 12-LNDE-coloring of $G$ , a contradiction.

Suppose that $n_{2} (v) = 2$ , say $d_{G} (v_{2}) = d_{G} (v_{3}) = 2$ . Let $v_{i}^{'}$ be the second neighbor of $v_{i}$ other than $v$ for each $i \in {2, 3}$ . We recolor $v v_{2}$ with a color $x \in C ∖ (C_{ϕ} (v_{2}^{'}) \cup C_{ϕ} (v) \cup C_{ϕ} (v_{3}))$ . Then there exists a color $a_{1} \in C_{ϕ} (v_{1}) ∖ (C_{ϕ} (v) \cup {x})$ . We color $u v$ with a color $b_{1} \in C ∖ (C_{ϕ} (u) \cup R (u) \cup {a_{1}, ϕ (v_{2} v_{2}^{'}), ϕ (v_{3} v_{3}^{'}), x})$ , and color $w v$ with a color $b_{2} \in C ∖ (C_{ϕ} (w) \cup R (w) \cup {a_{1}, ϕ (v_{2} v_{2}^{'}), ϕ (v_{3} v_{3}^{'}), x, b_{1}})$ to derive a 12-LNDE-coloring of $G$ , a contradiction.

Case 2. $C_{ϕ} (u) \neq C_{ϕ} (v)$ , $C_{ϕ} (w) = C_{ϕ} (v)$ .

Let $α \in C_{ϕ} (u) ∖ C_{ϕ} (v)$ . By Lemma 2.3, $| F (w_{1}) | \leq 8$ . Let $ϕ (w w_{i}) = b_{i}$ for $i \in {1, 2, 3}$ . We recolor $w w_{1}$ with a color $y \in C ∖ (F (w_{1}) \cup C_{ϕ} (v))$ . For each $i \in {2, 3}$ , if ${y, b_{2}, b_{3}} \subseteq C_{ϕ} (w_{i})$ , let $\bar{R} (w_{i}) = C_{ϕ} (w_{i}) ∖ C_{ϕ} (w)$ ; otherwise, let $\bar{R} (w_{i}) = \emptyset$ . We color $w v$ with a color $a_{1} \in C ∖ (C_{ϕ} (v) \cup R (v) \cup \bar{R} (w_{2}) \cup \bar{R} (w_{3}) \cup {α, y})$ , and color $u v$ with a color $a_{2} \in C ∖ (C_{ϕ} (u) \cup R (u) \cup C_{ϕ} (v) \cup R (v) \cup {a_{1}, y})$ to derive a 12-LNDE-coloring of $G$ , a contradiction.

Case 3. $C_{ϕ} (u) \neq C_{ϕ} (v)$ , $C_{ϕ} (w) \neq C_{ϕ} (v)$ .

Let $α \in C_{ϕ} (u) ∖ C_{ϕ} (v)$ and $β \in C_{ϕ} (w) ∖ C_{ϕ} (v)$ . Then we color $w v$ with a color $a_{1} \in C ∖ (C_{ϕ} (v) \cup R (v) \cup C_{ϕ} (w) \cup R (w) \cup {α})$ , and color $u v$ with a color $a_{2} \in C ∖ (C_{ϕ} (v) \cup R (v) \cup C_{ϕ} (u) \cup R (u) \cup {a_{1}, β})$ to derive a 12-LNDE-coloring of $G$ , a contradiction.

Claim 5. Let

v \in V (G)

with

d_{G} (v) = 5

. If

n_{3} (v) \geq 1

, then

n_{4^{-}} (v) \leq 3

Proof. Assume to the contrary that $n_{4^{-}} (v) \geq 4$ . Then $n_{5} (v) \leq 1$ . Let $v_{1}, v_{2}, \dots, v_{5}$ be the neighbors of $v$ with $d_{G} (v_{1}) = 3$ . Let $u_{1}$ and $u_{2}$ be the neighbors of $v_{1}$ other than $v$ . Then $R (v_{1}) = \emptyset$ by Claim 1.

Case 1. $n_{5} (v) = 1$ , say $d_{G} (v_{5}) = 5$ .

By Claim 3, $d_{G} (v_{i}) = 2$ for each $i \in {2, 3, 4}$ . Let $v_{i}^{'}$ be the neighbors of $v_{i}$ other than $v$ for $i \in {2, 3, 4}$ . By the minimality of $G$ , $G^{'} = G - {v v_{1}}$ has a 12-LNDE-coloring $ϕ$ using the color set $C$ .

Suppose that $C_{ϕ} (v_{1}) \subseteq C_{ϕ} (v)$ . Note that $n_{5} (v) = 1$ and $| C_{ϕ} (v_{1}) | = 2$ . Then ${ϕ (v v_{2}), ϕ (v v_{3}),$ $ϕ (v v_{4})} \cap C_{ϕ} (v_{1}) \neq \emptyset$ , say $ϕ (v v_{2}) \in C_{ϕ} (v_{1})$ . We recolor $v v_{2}$ with a color $x \in C ∖ (C_{ϕ} (v_{2}^{'}) \cup C_{ϕ} (v) \cup R (v))$ . Let $α \in C_{ϕ} (v_{5}) ∖ ((C_{ϕ} (v) - {ϕ (v v_{2})}) \cup {x})$ . Then we color $v v_{1}$ with a color $y \in C ∖ (C_{ϕ} (v) \cup R (v) \cup C_{ϕ} (v_{1}) \cup {x, α})$ to derive a 12-LNDE-coloring of $G$ , a contradiction. If $C_{ϕ} (v_{1}) ⊊ C_{ϕ} (v)$ . Then we color $v v_{1}$ with a color $y \in C ∖ (C_{ϕ} (v_{1}) \cup R (v_{1}) \cup C_{ϕ} (v) \cup R (v))$ to derive a 12-LNDE-coloring of $G$ , a contradiction.

Case 2. $n_{5} (v) = 0$ .

By Claim 3, $d_{G} (v_{i}) = 2$ for each $i \in {2, 3, 4, 5}$ . Let $v_{i}^{'}$ be the neighbors of $v_{i}$ other than $v$ for $i \in {2, 3, 4, 5}$ .

Suppose that $v_{2}^{'} = v_{3}^{'}$ . By the minimality of $G$ , $G^{'} = G - {v}$ has a 12-LNDE-coloring $ϕ$ using the color set $C$ . Let $ϕ (v_{i} v_{i}^{'}) = a_{i}$ for $i \in {2, 3, 4, 5}$ . Then we color $v v_{4}$ with a color $b_{4} \in C ∖ (C_{ϕ} (v_{4}^{'}) \cup C_{ϕ} (v_{1}) \cup {a_{2}, a_{3}, a_{5}})$ , color $v v_{5}$ with a color $b_{5} \in C ∖ (C_{ϕ} (v_{5}^{'}) \cup C_{ϕ} (v_{1}) \cup {a_{2}, a_{3}, a_{4}, b_{4}})$ , color $v v_{3}$ with a color $b_{3} \in C ∖ (C_{ϕ} (v_{3}^{'}) \cup C_{ϕ} (v_{1}) \cup {a_{4}, a_{5}, b_{4}, b_{5}})$ , color $v v_{2}$ with a color $b_{2} \in C ∖ (C_{ϕ} (v_{2}^{'}) \cup {a_{4}, a_{5}, b_{3}, b_{4}, b_{5}})$ , and color $v v_{1}$ with a color $b_{1} \in C ∖ (C_{ϕ} (v_{1}) \cup R (v_{1}) \cup {a_{2}, a_{3}, a_{4}, a_{5}, b_{2}, b_{3}, b_{4}, b_{5}})$ to derive a 12-LNDE-coloring of $G$ , a contradiction.

Suppose that $v_{2}^{'} \neq v_{3}^{'}$ . By Claim 2, $v_{2}^{'} v_{3}^{'} \notin E (G)$ . Let $G^{'}$ = $G - {v, v_{2}, v_{3}, v_{4}, v_{5}} + {v_{2}^{'} v_{3}^{'}}$ . By the minimality of $G$ , $G^{'}$ has a 12-LNDE-coloring $ϕ$ using the color set $C$ . Let $ϕ (v_{2}^{'} v_{3}^{'}) = a_{1}$ . Note that $a_{1} \in C_{ϕ} (v_{2}^{'}) \cap C_{ϕ} (v_{3}^{'})$ . We color $v_{2} v_{2}^{'}$ and $v_{3} v_{3}^{'}$ with the color $a_{1}$ . Then we color $v_{4} v_{4}^{'}$ with a color $a_{4} \in C ∖ (C_{ϕ} (v_{4}^{'}) \cup R (v_{4}^{'}) \cup {a_{1}})$ , color $v_{5} v_{5}^{'}$ with a color $a_{5} \in C ∖ (C_{ϕ} (v_{5}^{'}) \cup R (v_{5}^{'}) \cup {a_{1}})$ , color $v v_{4}$ with a color $b_{4} \in C ∖ (C_{ϕ} (v_{4}^{'}) \cup C_{ϕ} (v_{1}) \cup {a_{1}, a_{5}})$ , color $v v_{5}$ with a color $b_{5} \in C ∖ (C_{ϕ} (v_{5}^{'}) \cup C_{ϕ} (v_{1}) \cup {a_{1}, a_{4}, b_{4}})$ , color $v v_{3}$ with a color $b_{3} \in C ∖ (C_{ϕ} (v_{3}^{'}) \cup C_{ϕ} (v_{1}) \cup {a_{4}, a_{5}, b_{4}, b_{5}})$ , color $v v_{2}$ with a color $b_{2} \in C ∖ (C_{ϕ} (v_{2}^{'}) \cup {a_{4}, a_{5}, b_{3}, b_{4}, b_{5}})$ , and color $v v_{1}$ with a color $b_{1} \in C ∖ (C_{ϕ} (v_{1}) \cup R (v_{1}) \cup {a_{1}, a_{4}, a_{5}, b_{2}, b_{3}, b_{4}, b_{5}})$ to derive a 12-LNDE-coloring of $G$ , a contradiction.

Claim 6.

G

does not contain any vertex of degree

3

Proof. Assume to the contrary that $G$ contain a $3$ -vertex $v$ . Let $v_{1}, v_{2}, v_{3}$ be the neighbors of $v$ . By Claim 1 and Claim 5, $d_{G} (v_{i}) = 5$ and $n_{4^{-}} (v_{i}) \leq 3$ for each $i \in {1, 2, 3}$ . By the minimality of $G$ , $G^{'} = G - {v}$ has a 12-LNDE-coloring $ϕ$ using the color set $C$ . Then $| R (v_{i}) | \leq 2$ . Suppose that $C_{ϕ} (v_{1}) \cap C_{ϕ} (v_{2}) \neq \emptyset$ . Then we color $v v_{2}$ with a color $b \in C ∖ (C_{ϕ} (v_{2}) \cup R (v_{2}) \cup C_{ϕ} (v_{3}))$ , color $v v_{3}$ with a color $c \in C ∖ (C_{ϕ} (v_{3}) \cup R (v_{3}) \cup C_{ϕ} (v_{1}) \cup {b})$ , and color $v v_{1}$ with a color $a \in C ∖ (C_{ϕ} (v_{1}) \cup R (v_{1}) \cup C_{ϕ} (v_{2}) \cup {b, c})$ to derive a 12-LNDE-coloring of $G$ , a contradiction. So suppose that $C_{ϕ} (v_{1}) \cap C_{ϕ} (v_{2}) = \emptyset$ . By symmetry, $C_{ϕ} (v_{2}) \cap C_{ϕ} (v_{3}) = \emptyset$ and $C_{ϕ} (v_{1}) \cap C_{ϕ} (v_{3}) = \emptyset$ . That is $C_{ϕ} (v_{1}) = {a_{1}, a_{2}, a_{3}, a_{4}}$ , $C_{ϕ} (v_{2}) = {a_{5}, a_{6}, a_{7}, a_{8}}$ and $C_{ϕ} (v_{3}) = {a_{9}, a_{10}, a_{11}, a_{12}}$ . Obviously $R (v_{1}) \cap C_{ϕ} (v_{2}) \neq \emptyset$ or $R (v_{1}) \cap C_{ϕ} (v_{3}) \neq \emptyset$ , say $R (v_{1}) \cap C_{ϕ} (v_{2}) \neq \emptyset$ . Then we color $v v_{2}$ with a color $b \in C ∖ (C_{ϕ} (v_{2}) \cup R (v_{2}) \cup C_{ϕ} (v_{3}))$ , color $v v_{3}$ with a color $c \in C ∖ (C_{ϕ} (v_{3}) \cup R (v_{3}) \cup C_{ϕ} (v_{1}) \cup {b})$ , and color $v v_{1}$ with a color $a \in C ∖ (C_{ϕ} (v_{1}) \cup R (v_{1}) \cup C_{ϕ} (v_{2}) \cup {b, c})$ to derive a 12-LNDE-coloring of $G$ , a contradiction.

Claim 7. Let

v \in V (G)

with

d_{G} (v) = 5

. If

n_{4} (v) \geq 1

, then

n_{4^{-}} (v) \leq 2

Proof. Assume to the contrary that $n_{4^{-}} (v) \geq 3$ then $n_{5} (v) \leq 2$ . Let $v_{1}, v_{2}, \dots, v_{5}$ be the neighbors of $v$ with $d_{G} (v_{1}) = 4$ . Let $u_{1}, u_{2}, u_{3}$ be the neighbors of $v_{1}$ other than $v$ . Then $R (v_{1}) = \emptyset$ by Claim 1.

Case 1. $n_{5} (v) \geq 1$ , say $d_{G} (v_{5}) = 5$ .

By Claim 4 and Claim 6, $n_{2} (v) \geq 2$ . Let $d_{G} (v_{i}) = 2$ and $v_{i}^{'}$ be the second neighbor of $v_{i}$ other than $v$ for $i \in {2, 3}$ . By the minimality of $G$ , $G^{'} = G - {v v_{1}}$ has a 12-LNDE-coloring $ϕ$ using the color set $C$ .

Suppose that $C_{ϕ} (v_{1}) \subseteq C_{ϕ} (v)$ . Note that $n_{5} (v) \leq 2$ and $| C_{ϕ} (v_{1}) | = 3$ . Then ${ϕ (v v_{2}), ϕ (v v_{3})}$ $\cap C_{ϕ} (v_{1}) \neq \emptyset$ , say $ϕ (v v_{2}) \in C_{ϕ} (v_{1})$ . We recolor $v v_{2}$ with a color $x \in C ∖ (C_{ϕ} (v_{2}^{'}) \cup R (v) \cup C_{ϕ} (v))$ . Let $α_{i} \in C_{ϕ} (v_{i}) ∖ ((C_{ϕ} (v) - {ϕ (v v_{2})}) \cup {x})$ , when $d_{G} (v_{i}) = 5$ . If $d_{G} (v_{4}) = 5$ , then we color $v v_{1}$ with a color $y \in C ∖ (C_{ϕ} (v) \cup {x, α_{4}, α_{5}, ϕ (v_{3} v_{3}^{'}), ϕ (v_{2} v_{2}^{'})})$ to derive a 12-LNDE-coloring of $G$ , a contradiction. If $d_{G} (v_{4}) \leq 4$ , by Claim 4 and Claim 6, we have $d_{G} (v_{4}) = 2$ . Let $v_{4}^{'}$ be the second neighbor of $v_{4}$ other than $v$ . Then we color $v v_{1}$ with a color $y \in C ∖ (C_{ϕ} (v) \cup {x, α_{5}, ϕ (v_{2} v_{2}^{'}), ϕ (v_{3} v_{3}^{'}), ϕ (v_{4} v_{4}^{'})})$ to derive a 12-LNDE-coloring of $G$ , a contradiction. If $C_{ϕ} (v_{1}) ⊊ C_{ϕ} (v)$ . We color $v v_{1}$ with a color $y \in C ∖ (C_{ϕ} (v_{1}) \cup R (v_{1}) \cup C_{ϕ} (v) \cup R (v))$ to derive a 12-LNDE-coloring of $G$ , a contradiction.

Case 2. $n_{5} (v) = 0$ .

By Claim 4 and Claim 6, $d_{G} (v_{i}) = 2$ for $i \in {2, 3, 4, 5}$ , let $v_{i}^{'}$ be the second neighbor of $v_{i}$ other than $v$ .

Suppose that $v_{2}^{'} = v_{3}^{'}$ . By the minimality of $G$ , $G^{'} = G - {v}$ has a 12-LNDE-coloring $ϕ$ using the color set $C$ . Let $ϕ (v_{i} v_{i}^{'}) = a_{i}$ for $i \in {2, 3, 4, 5}$ . Then we color $v v_{2}$ with a color $b_{2} \in C ∖ (C_{ϕ} (v_{2}^{'}) \cup C_{ϕ} (v_{1}) \cup {a_{4}, a_{5}})$ , color $v v_{3}$ with a color $b_{3} \in C ∖ (C_{ϕ} (v_{3}^{'}) \cup C_{ϕ} (v_{1}) \cup {a_{4}, a_{5}, b_{2}})$ , color $v v_{4}$ with a color $b_{4} \in C ∖ (C_{ϕ} (v_{4}^{'}) \cup {a_{2}, a_{3}, a_{5}, b_{2}, b_{3}})$ , color $v v_{5}$ with a color $b_{5} \in C ∖ (C_{ϕ} (v_{5}^{'}) \cup {a_{2}, a_{3}, a_{4}, b_{2}, b_{3}, b_{4}})$ , and color $v v_{1}$ with a color $b_{1} \in C ∖ (C_{ϕ} (v_{1}) \cup R (v_{1}) \cup {a_{2}, a_{3}, a_{4}, a_{5}, b_{2}, b_{3}, b_{4}, b_{5}})$ . Note that ${b_{2}, b_{3}} \notin C_{ϕ} (v_{1})$ , then $C_{ϕ} (v_{1}) ⊊ C_{ϕ} (v)$ . Hence, the obtained coloring is the 12-LNDE-coloring of $G$ , a contradiction.

Suppose that $v_{2}^{'} \neq v_{3}^{'}$ . By Claim 2, $v_{2}^{'} v_{3}^{'} \notin E (G)$ . Let $G^{'}$ = $G - {v, v_{2}, v_{3}, v_{4}, v_{5}} + {v_{2}^{'} v_{3}^{'}}$ . By the minimality of $G$ , $G^{'}$ has a 12-LNDE-coloring $ϕ$ using the color set $C$ . Let $ϕ (v_{1}^{'} v_{2}^{'}) = a_{1}$ . Note that $a_{1} \in C_{ϕ} (v_{2}^{'}) \cap C_{ϕ} (v_{3}^{'})$ . Then we color $v_{2} v_{2}^{'}$ and $v_{3} v_{3}^{'}$ with the color $a_{1}$ . Now, we color $v_{4} v_{4}^{'}$ with a color $a_{4} \in C ∖ (C_{ϕ} (v_{4}^{'}) \cup R (v_{4}^{'}) \cup {a_{1}})$ , color $v_{5} v_{5}^{'}$ with a color $a_{5} \in C ∖ (C_{ϕ} (v_{5}^{'}) \cup R (v_{5}^{'}) \cup {a_{1}})$ , color $v v_{2}$ with a color $b_{2} \in C ∖ (C_{ϕ} (v_{2}^{'}) \cup C_{ϕ} (v_{1}) \cup {a_{4}, a_{5}})$ , color $v v_{3}$ with a color $b_{3} \in C ∖ (C_{ϕ} (v_{3}^{'}) \cup C_{ϕ} (v_{1}) \cup {a_{4}, a_{5}, b_{2}})$ , color $v v_{4}$ with a color $b_{4} \in C ∖ (C_{ϕ} (v_{4}^{'}) \cup {a_{1}, a_{5}, b_{2}, b_{3}})$ , color $v v_{5}$ with a color $b_{5} \in C ∖ (C_{ϕ} (v_{5}^{'}) \cup {a_{1}, a_{4}, b_{2}, b_{3}, b_{4}})$ , and color $v v_{1}$ with a color $b_{1} \in C ∖ (C_{ϕ} (v_{1}) \cup {a_{1}, a_{4}, a_{5}, b_{2}, b_{3}, b_{4}, b_{5}})$ . Note that ${b_{2}, b_{3}} \notin C_{ϕ} (v_{1})$ , then $C_{ϕ} (v_{1}) ⊊ C_{ϕ} (v)$ . Hence, the obtained coloring is the 12-LNDE-coloring of $G$ , a contradiction.

Claim 8.

G

does not contain any vertex of degree

4

Proof. Assume to the contrary that $G$ contain a $4$ -vertex $v$ . Let $v_{1}, v_{2}, v_{3}, v_{4}$ be the neighbors of $v$ . By Claim 1 and Claim 7, $d_{G} (v_{i}) = 5$ and $n_{4^{-}} (v_{i}) \leq 2$ for $i \in {1, 2, 3, 4}$ . By the minimality of $G$ , $G^{'} = G - {v}$ has a 12-LNDE-coloring $ϕ$ using the color set $C$ . Then $| R (v_{i}) | \leq 1$ . Note that $| C_{ϕ} (v_{i}) | = 4$ for each $i \in {1, 2, 3, 4}$ . Then there exist colors $i, j \in {1, 2, 3, 4}$ such that $C_{ϕ} (v_{i}) \cap C_{ϕ} (v_{j}) \neq \emptyset$ , say $C_{ϕ} (v_{1}) \cap C_{ϕ} (v_{2}) \neq \emptyset$ . Now, we color $v v_{2}$ with a color $b \in C ∖ (C_{ϕ} (v_{2}) \cup R (v_{2}) \cup C_{ϕ} (v_{3}))$ , color $v v_{3}$ with a color $c \in C ∖ (C_{ϕ} (v_{3}) \cup R (v_{3}) \cup C_{ϕ} (v_{4}) \cup {b})$ , color $v v_{4}$ with a color $d \in C ∖ (C_{ϕ} (v_{4}) \cup R (v_{4}) \cup C_{ϕ} (v_{1}) \cup {b, c})$ , and color $v v_{1}$ with a color $a \in C ∖ (C_{ϕ} (v_{1}) \cup R (v_{1}) \cup C_{ϕ} (v_{2}) \cup {b, c, d})$ . Note that $C_{ϕ} (v_{1}) \cap C_{ϕ} (v_{2}) \neq ϕ$ , then $| C ∖ (C_{ϕ} (v_{1}) \cup R (v_{1}) \cup C_{ϕ} (v_{2}) \cup {b, c, d}) | \geq 12 - 4 - 1 - 4 - 3 + 1 = 1$ . Hence, the obtained coloring is the 12-LNDE-coloring of $G$ , a contradiction.

Claim 9.

G

does not contain a

4

-cycle

C_{4} = v_{1} v_{2} v_{3} v_{4} v_{1}

with

d_{G} (v_{1}) = d_{G} (v_{3}) = 2

and

d_{G} (v_{2}) = d_{G} (v_{4}) = 5

Proof. Assume to the contrary that such a $4$ -cycle $C_{4}$ exists. Let $u_{1}, u_{2}, u_{3}$ be the neighbors of $v_{2}$ not in $C_{4}$ and $w_{1}, w_{2}, w_{3}$ be the neighbors of $v_{4}$ not in $C_{4}$ .

Case 1. $n_{5} (v_{2}) \geq 1$ or $n_{5} (v_{4}) \geq 1$ , say $n_{5} (v_{2}) \geq 1$ .

By the minimality of $G$ , $G^{'} = G - {v_{1}, v_{3}}$ has a 12-LNDE-coloring $ϕ$ using the color set $C$ . Then $| R (v_{2}) | \leq 2$ . We color $v_{1} v_{4}$ with a color $a \in C ∖ (C_{ϕ} (v_{4}) \cup R (v_{4}) \cup C_{ϕ} (v_{2}))$ , color $v_{3} v_{4}$ with a color $b \in C ∖ (C_{ϕ} (v_{4}) \cup R (v_{4}) \cup C_{ϕ} (v_{2}) \cup {a})$ , color $v_{2} v_{3}$ with a color $c \in C ∖ (C_{ϕ} (v_{4}) \cup C_{ϕ} (v_{2}) \cup R (v_{2}) \cup {a, b})$ , and color $v_{1} v_{2}$ with a color $d \in C ∖ (C_{ϕ} (v_{4}) \cup C_{ϕ} (v_{2}) \cup R (v_{2}) \cup {a, b, c})$ to derive a 12-LNDE-coloring of $G$ , a contradiction.

Case 2. $n_{5} (v_{2}) = n_{5} (v_{4}) = 0$ .

By Claim 6 and Claim 8, $d_{G} (u_{i}) = 2$ . For each $i \in {1, 2, 3}$ , let $u_{i}^{'}$ be the second neighbor of $u_{i}$ other than $v_{2}$ , and $w_{i}^{'}$ be the second neighbor of $w_{i}$ other than $v_{4}$ . For each $i \in {1, 2, 3}$ , if $u_{i} = w_{i}$ , then $G ≅ K_{2, n}$ and $G$ has a 12-LNDE-coloring, a contradiction. So we may suppose that $u_{1} \neq w_{1}$ . By Claim 2, $u_{1} w_{1} \notin E (G)$ . Let $G^{'} = G - {v_{1}, v_{2}, v_{3}, v_{4}}$ . By the minimality of $G$ , $G^{'}$ has a 12-LNDE-coloring $ϕ$ using the color set $C$ . Let $ϕ (u_{i} u_{i}^{'}) = a_{i}$ and $ϕ (w_{i} w_{i}^{'}) = b_{i}$ for $i \in {1, 2, 3}$ . Then we color $v_{2} u_{1}$ and $v_{4} w_{1}$ with a color $α \in C ∖ (C_{ϕ} (u_{1}^{'}) \cup C_{ϕ} (w_{1}^{'}))$ , Color $v_{4} w_{2}$ with a color $c_{1} \in C ∖ (C_{ϕ} (w_{2}^{'}) \cup {α, b_{1}, b_{3}})$ , $v_{4} w_{3}$ with a color $c_{2} \in C ∖ (C_{ϕ} (w_{3}^{'}) \cup {α, b_{1}, b_{2}, c_{1}})$ , color $v_{2} u_{2}$ with a color $c_{3} \in C ∖ (C_{ϕ} (u_{2}^{'}) \cup {α, a_{1}, a_{3}, c_{1}, c_{2}})$ , color $v_{2} u_{3}$ with a color $c_{4} \in C ∖ (C_{ϕ} (u_{3}^{'}) \cup {α, a_{1}, a_{2}, c_{1}, c_{2}, c_{3}})$ , color $v_{1} v_{4}$ with a color $d_{1} \in C ∖ {α, c_{1}, c_{2}, c_{3}, c_{4}, b_{1}, b_{2}, b_{3}}$ , color $v_{3} v_{4}$ with a color $d_{2} \in C ∖ {α, c_{1}, c_{2}, c_{3}, c_{4}, b_{1}, b_{2}, b_{3}, d_{1}}$ , color $v_{1} v_{2}$ with a color $d_{3} \in C ∖ {α, c_{1}, c_{2}, c_{3}, c_{4}, a_{1}, a_{2}, a_{3}, d_{1}, d_{2}}$ , and color $v_{2} v_{3}$ with a color $d_{4} \in C ∖ {α, c_{1}, c_{2}, c_{3}, c_{4}, a_{1}, a_{2}, a_{3}, d_{1}, d_{2}, d_{3}}$ to derive a 12-LNDE-coloring of $G$ , a contradiction.

Claim 10.

G

does not contain a path

P_{5} = v_{1} v_{2} v_{3} v_{4} v_{5}

with

d_{G} (v_{1}) = d_{G} (v_{3}) = d_{G} (v_{5}) = 5

and

d_{G} (v_{2}) = d_{G} (v_{4}) = 2

Proof. Assume to the contrary that such a path $P_{5} = v_{1} v_{2} v_{3} v_{4} v_{5}$ exists. Let $u_{1}, u_{2}, u_{3}$ be the neighbors of $v_{3}$ not in $P_{5}$ . Then $v_{1} v_{5} \notin E (G)$ by Claim 2.

Case 1. $n_{5} (v_{3}) \geq 2$ .

By the minimality of $G$ , $G^{'} = G - {v_{2}, v_{4}}$ has a 12-LNDE-coloring $ϕ$ using the color set $C$ . Then $| R (v_{3}) | \leq 1$ . We color $v_{1} v_{2}$ with a color $a \in C ∖ (C_{ϕ} (v_{1}) \cup R (v_{1}) \cup C_{ϕ} (v_{3}))$ , color $v_{4} v_{5}$ with a color $b \in C ∖ (C_{ϕ} (v_{5}) \cup R (v_{5}) \cup C_{ϕ} (v_{3}))$ , color $v_{2} v_{3}$ with a color $c \in C ∖ (C_{ϕ} (v_{1}) \cup C_{ϕ} (v_{3}) \cup R (v_{3}) \cup {a, b})$ , and color $v_{3} v_{4}$ with a color $d \in C ∖ (C_{ϕ} (v_{5}) \cup C_{ϕ} (v_{3}) \cup R (v_{3}) \cup {a, b, c})$ to derive a 12-LNDE-coloring of $G$ , a contradiction.

Case 2. $n_{5} (v_{3}) = 1$ , say $d_{G} (u_{3}) = 5$ .

By Claim 6 and Claim 8, $d_{G} (u_{1}) = d_{G} (u_{2}) = 2$ . Let $u_{i}^{'}$ be the second neighbor of $u_{i}$ other than $v_{3}$ for each $i \in {1, 2}$ . Let $G^{'}$ = $G - {v_{2}, v_{3}, v_{4}, u_{1}, u_{2}} + v_{1} v_{5}$ . By the minimality of $G$ , $G^{'}$ has a 12-LNDE-coloring $ϕ$ using the color set $C$ . Let $ϕ (v_{1} v_{5}) = α$ . We color $v_{1} v_{2}$ and $v_{4} v_{5}$ with the color $α$ , color $v_{3} u_{1}$ with a color $a_{1} \in C ∖ (C_{ϕ} (u_{1}^{'}) \cup C_{ϕ} (u_{3}) \cup {α})$ , color $v_{3} u_{3}$ with a color $a_{3} \in C ∖ (C_{ϕ} (u_{3}) \cup R (u_{3}) \cup {α, a_{1}})$ , color $v_{3} u_{2}$ with a color $a_{2} \in C ∖ (C_{ϕ} (u_{2}^{'}) \cup {α, a_{1}, a_{3}})$ , color $u_{1} u_{1}^{'}$ with a color $b_{1} \in C ∖ (C_{ϕ} (u_{1}^{'}) \cup R (u_{1}^{'}) \cup {a_{1}, a_{2}, a_{3}})$ , color $u_{2} u_{2}^{'}$ with a color $b_{2} \in C ∖ (C_{ϕ} (u_{2}^{'}) \cup R (u_{2}^{'}) \cup {a_{1}, a_{2}, a_{3}})$ , color $v_{3} v_{2}$ with a color $a_{4} \in C ∖ (C_{ϕ} (v_{1}) \cup {α, a_{1}, a_{2}, a_{3}, b_{1}, b_{2}})$ , and color $v_{3} v_{4}$ with a color $a_{5} \in C ∖ (C_{ϕ} (v_{5}) \cup {α, a_{1}, a_{2}, a_{3}, a_{4}, b_{1}, b_{2}})$ to derive a 12-LNDE-coloring of $G$ , a contradiction.

Case 3. $n_{5} (v_{3}) = 0$ .

By Claim 6 and Claim 8, $d_{G} (u_{1}) = d_{G} (u_{2}) = d_{G} (u_{3}) = 2$ . For each $i \in {1, 2, 3}$ , let $u_{i}^{'}$ be the second neighbor of $u_{i}$ other than $v_{3}$ . By Claim 2 and Claim 9, $u_{1}^{'} u_{2}^{'} \notin E (G)$ and $u_{1}^{'} \neq u_{2}^{'}$ . Let $G^{'}$ = $G - {v_{2}, v_{3}, v_{4}, u_{1}, u_{2}, u_{3}} + {v_{1} v_{5}, u_{1}^{'} u_{2}^{'}}$ . By the minimality of $G$ , $G^{'}$ has a 12-LNDE-coloring $ϕ$ using the color set $C$ . Let $ϕ (v_{1} v_{5}) = α$ and $ϕ (u_{1}^{'} u_{2}^{'}) = β$ . We color $v_{1} v_{2}$ and $v_{4} v_{5}$ with the color $α$ , color $u_{1} u_{1}^{'}$ and $u_{2} u_{2}^{'}$ with the color $β$ , color $u_{3} u_{3}^{'}$ with a color $γ \in C ∖ (C_{ϕ} (u_{3}^{'}) \cup R (u_{3}^{'}))$ , color $v_{3} u_{1}$ with a color $a_{1} \in C ∖ (C_{ϕ} (u_{1}^{'}) \cup {α, β, γ})$ , color $v_{3} u_{2}$ with a color $a_{2} \in C ∖ (C_{ϕ} (u_{2}^{'}) \cup {α, β, γ, a_{1}})$ , color $v_{3} u_{3}$ with a color $a_{3} \in C ∖ (C_{ϕ} (u_{3}^{'}) \cup {α, β, γ, a_{1}, a_{2}})$ , color $v_{3} v_{2}$ with a color $a_{4} \in C ∖ (C_{ϕ} (v_{1}) \cup {α, β, γ, a_{1}, a_{2}, a_{3}})$ , and color $v_{3} v_{4}$ with a color $a_{5} \in C ∖ (C_{ϕ} (v_{5}) \cup {α, β, γ, a_{1}, a_{2}, a_{3}, a_{4}})$ to derive a 12-LNDE-coloring of $G$ , a contradiction.

Claim 11.

G

does not contain any vertex of degree

2

Proof. Assume to the contrary that $G$ contain a $2$ -vertex $v$ . Let $v_{1}, v_{2}$ be the neighbors of $v$ . By Claim 1 $d_{G} (v_{1}) = d_{G} (v_{2}) = 5$ . By Claim 6 and Claim 8-10, $n_{4^{-}} (v_{1}) = n_{4^{-}} (v_{2}) = 0$ . By the minimality of $G$ , $G^{'} = G - {v}$ has a 12-LNDE-coloring $ϕ$ using the color set $C$ . Then $R (v_{1}) = R (v_{2}) = \emptyset$ . We color $v v_{1}$ with a color $a \in C ∖ (C_{ϕ} (v_{1}) \cup R (v_{1}) \cup C_{ϕ} (v_{2}))$ , and color $v v_{2}$ with a color $b \in C ∖ (C_{ϕ} (v_{1}) \cup C_{ϕ} (v_{2}) \cup R (v_{2}) \cup {a})$ to derive a 12-LNDE-coloring of $G$ , a contradiction.

Now it follows from Claim 1-11 that $G$ is $5$ -regular. But, by Lemma 2.1 and Proposition 1, $G$ is $10$ -LNDE-colorable, a contradiction. So we complete the proof of Theorem 1.6.

Funding

The first author’s research is supported by NSFC (No. 12171436, 12371360) and Natural Science Foundation of Zhejiang Province (No. LZ23A010004); The third author’s research is supported by NSFC (No. 12031018).

References:

S. Akbari, H. Bidkhori, and N. Nosrati. R-strong edge colorings of graphs. Discrete Mathematics, 306(23):3005–3010, 2006. https://doi.org/10.1016/j.disc.2004.12.027.
J. Gu. Strict neighbor-distinguishing edge-coloring of graphs, (in Chinese). Zhejiang Normal University, 2021.
J. Gu, W. Wang, Y. Wang, and Y. Wang. Strict neighbor-distinguishing index of subcubic graphs. Graphs and Combinatorics, 37:355–368, 2021. https://doi.org/10.1007/s00373-020-02246-w.
J. Gu, Y. Wang, W. Wang, and L. Zheng. Strict neighbor-distinguishing index of k4-minor-free graphs. Discrete Applied Mathematics, 329:87–95, 2023. https://doi.org/10.1016/j.dam.2023.01.017.
H. Hatami. Δ + 300 is a bound on the adjacent vertex distinguishing edge chromatic number. Journal of Combinatorial Theory, Series B, 95(2):246–256, 2005. https://doi.org/10.1016/j.jctb.2005.04.002.
D. Huang, H. Cai, W. Wang, and J. Huo. Neighbor-distinguishing indices of planar graphs with maximum degree ten. Discrete Applied Mathematics, 329:49–60, 2023. https://doi.org/10.1016/j.dam.2022.12.023.

G. Joret and W. Lochet. Progress on the adjacent vertex distinguishing edge coloring conjecture. SIAM Journal on Discrete Mathematics, 34(4):2221–2238, 2020. https://doi.org/10.1137/18M1200427.
B. Vučković. Edge-partitions of graphs and their neighbor-distinguishing index. Discrete Mathematics, 340(12):3092–3096, 2017. https://doi.org/10.1016/j.disc.2017.07.005.
W. Wang, W. Xia, J. Huo, and Y. Wang. On the neighbor-distinguishing indices of planar graphs. Bulletin of the Malaysian Mathematical Sciences Society, 45(2):677–696, 2022. https://doi.org/10.1007/s40840-021-01213-9.
Y. Wang, W. Wang, and J. Huo. Some bounds on the neighbor-distinguishing index of graphs. Discrete Mathematics, 338(11):2006–2013, 2015. https://doi.org/10.1016/j.disc.2015.05.007.
Z. Zhang, L. Liu, and J. Wang. Adjacent strong edge coloring of graphs. Applied Mathematics Letters, 15(5):623–626, 2002. https://doi.org/10.1016/S0893-9659(02)80015-5.
E. Zhu, Z. Wang, and Z. Zhang. On the smarandachely-adjacent-vertex edge coloring of some double graphs. Shandong University (Natural Science), 44:12, 2009.

[1] S. Akbari, H. Bidkhori, and N. Nosrati. R-strong edge colorings of graphs. Discrete Mathematics, 306(23):3005–3010, 2006. https://doi.org/10.1016/j.disc.2004.12.027.

[2] J. Gu. Strict neighbor-distinguishing edge-coloring of graphs, (in Chinese). Zhejiang Normal University, 2021.

[3] J. Gu, W. Wang, Y. Wang, and Y. Wang. Strict neighbor-distinguishing index of subcubic graphs. Graphs and Combinatorics, 37:355–368, 2021. https://doi.org/10.1007/s00373-020-02246-w.

[4] J. Gu, Y. Wang, W. Wang, and L. Zheng. Strict neighbor-distinguishing index of k4-minor-free graphs. Discrete Applied Mathematics, 329:87–95, 2023. https://doi.org/10.1016/j.dam.2023.01.017.

[5] H. Hatami. Δ + 300 is a bound on the adjacent vertex distinguishing edge chromatic number. Journal of Combinatorial Theory, Series B, 95(2):246–256, 2005. https://doi.org/10.1016/j.jctb.2005.04.002.

[6] D. Huang, H. Cai, W. Wang, and J. Huo. Neighbor-distinguishing indices of planar graphs with maximum degree ten. Discrete Applied Mathematics, 329:49–60, 2023. https://doi.org/10.1016/j.dam.2022.12.023.

Contents

Ars Combinatoria

The strict neighbor-distinguishing index of simple graphs with maximum degree five

Abstract

1. Introduction

2. Main results

Funding

References:

Information

Guidelines

CP Initiatives

Follow CP