Suppose that \(\phi\) is a proper edge-\(k\)-coloring of the graph \(G\). For a vertex \(v \in V(G)\), let \(C_\phi(v)\) denote the set of colors assigned to the edges incident with \(v\). The proper edge-\(k\)-coloring \(\phi\) of \(G\) is strict neighbor-distinguishing if for any adjacent vertices \(u\) and \(v\), \(C_\phi(u) \varsubsetneq C_\phi(v)\) and \(C_\phi(v) \varsubsetneq C_\phi(u)\). The strict neighbor-distinguishing index, denoted \(\chi’_{snd}(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 \(\chi’_{snd}(G) \leq 12\).
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 \(\delta(G)\) and \(\Delta(G)\) (for short \(\Delta\)) 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 \(\phi:E(G)\rightarrow\{1,2,…,k\}\) such that any two adjacent edges receive different colors. The chromatic index \(\chi'(G)\) of \(G\) is the smallest integer \(k\) such that \(G\) has a proper edge-\(k\)-coloring. Given a proper edge-\(k\)-coloring \(\phi\) of \(G\), we use \(C_\phi{(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 \(\phi\), if \(C_\phi(v)\subsetneq{C_\phi(u)}\) and \(C_\phi(u)\subsetneq{C_\phi(v)}\). The proper edge-\(k\)-coloring \(\phi\) is neighbor-distinguishing if \(C_\phi{(u)}\neq C_\phi{(v)}\) for any \(uv\in E(G)\). The neighbor-distinguishing index \(\chi'_{a}(G)\) is the smallest integer \(k\) such that \(G\) has a neighbor-distinguishing edge-\(k\)-coloring. The proper edge-\(k\)-coloring \(\phi\) is strict neighbor-distinguishing if any two adjacent vertices are exclusive. The strict neighbor-distinguishing index \(\chi'_{snd}(G)\) is the smallest integer \(k\) such that \(G\) has a strict neighbor-distinguishing edge-\(k\)-coloring. The proper edge-\(k\)-coloring \(\phi\) is local neighbor-distinguishing (for short, \(k\)-LNDE-coloring) if any two adjacent \(2^+\)-vertices are exclusive. The local neighbor-distinguishing index \(\chi'_{lnd}(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 \(\delta(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 \(\chi'_{snd}(G)\geq \chi'_a(G)\geq \Delta\) for any formal graph \(G\). Moreover, the following propositions hold obviously.
Zhang et al. [11] introduced the neighbor-distinguishing edge-coloring and proposed the following conjecture.
Akbari et al. 1] proved that every normal graph \(G\) satisfies \(\chi'_a(G)\leq 3\Delta\). The upper bound was improved to \(2.5\Delta\) by Wang et al. 10], and to \(2\Delta+2\) by Vučković 8]. In 2005, Hatami 5] showed that every normal graph \(G\) with \(\Delta > 10^{20}\) has \(\chi'_a(G)\leq \Delta+300\). Joret and Lochet 7] improved this result to that \(\chi'_a(G)\leq \Delta+19\) for any normal graph \(G\) with sufficiently large \(\Delta\). Huang et al. 6] showed that \(\chi'_a(G)\leq \Delta+2\) for any normal planar graph \(G\) with \(\Delta\geq 10\). Moreover, Wang et al. 9] showed that \(\Delta\leq \chi'_a(G)\leq \Delta+1\) for any normal planar graph \(G\) with \(\Delta\geq 14\), and \(\chi'_a(G)=\Delta+1\) if and only if \(G\) contains adjacent \(\Delta\)-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\geq2)\) 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 \(\chi'_{snd}(H_{n})\)=\(2n+1\)=\(2\Delta(H_{n})+1\). Based on these facts, Gu et al. 3] proposed the following conjecture.
Since \(\chi'_{snd}(K_{2,n})\)=\(2n\)=\(2\Delta(K_{2,n})\), the upper bound \(2\Delta\) in Conjecture 1.4 is tight. Gu et al. 3] proved that the Conjecture 1.4 holds for the graphs with \(\Delta\leq3\). Recently, Gu et al. 4] proved that the Conjecture 1.4 holds for \(K_{4}\)-minor-free graphs. Moreover, Gu 2] proved that \(\chi'_{snd}(G)\leq 9\) for the formal graph \(G\) with \(\Delta\leq 4\).
In this paper, we show that \(\chi'_{snd}(G)\leq 12\) for a formal graph \(G\) with \(\Delta\leq 5\). That is, we show the following theorem.
This section is devoted to show the main result in this paper. For an LNDE-coloring \(\phi\), set \(R(v)=\{r_i\in C_\phi(u_i)\setminus C_\phi(v)|u_iv\in E(G)\) and \(d_G(u_i)< d_G(v)\}\).
We introduce some useful lemmas.
Proof. Let \(w\in N_G(u_1)\setminus\{u\}\). Since \(w\) and \(u_1\) are exclusive in \(\phi\), there exists a color \(\alpha\in{C_\phi(w)\setminus C_\phi(u_1)}\). Suppose that \(uu_1\) can be recolored with a color \(x\). Then \(x\notin C_\phi(u_1)-\{\phi(uu_1)\}\). If \(C_\phi(u_1)-\{x\}\subseteq{C_\phi(w)}\), then \(x\notin C_\phi(w)-(C_\phi(u_1)-\{\phi(uu_1)\})\). If \(C_\phi(u_1)-\{\phi(uu_1)\}\nsubseteq{C_\phi(w)}\), then \(x\neq \alpha\). Therefore, \[|F(u_1)|\leq \sum\limits_{w\in{N_G(u_1)\setminus\{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 \(\chi'_{lnd}(G)\geq 13\). But for each graph \(G'\) with \(|E(G')|<|E(G)|\) and \(\Delta(G')\leq 5\), we have \(\chi'_{lnd}(G')\leq 12\).
Assume that \(\delta(G)=1\). Let \(uv\in E(G)\) with \(d_G(u)=1\). By the minimality of \(G\), \(G'=G-\{u\}\) has a 12-LNDE-coloring \(\phi\) 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 \(uv\) with a color \(a\in C\setminus C_\phi(v')\) to derive a 12-LNDE-coloring of \(G\), a contradiction. Suppose that \(d_G(v)\geq 3\). Then we can color \(uv\) with a color \(b\in C\setminus (C_\phi(v)\cup R(v))\). Since \(|C\setminus (C_\phi(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 \(\delta(G)\geq 2\) in the following discussion.
To complete the proof, we have to establish a series of auxiliary claims.
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,\cdots,u_{d-1}\}\) and \(N_G(v)=\{u,v_1,\cdots,v_{t-1}\}\).
Case 1. \(d=2\).
By the minimality of \(G\), \(G'=G-\{u\}\) has a 12-LNDE-coloring \(\phi\) using the color set \(C\).
Suppose that \(t=2\). If \(d_G(u_1)=2\) with \(N_G(u_1)=\{u,x\}\), then color \(uu_1\) with a color \(a\in C\setminus(C_\phi(x)\cup{C_\phi(v)})\) and color \(uv\) with a color \(b\in C\setminus(C_\phi(v_1)\cup{\{\phi(u_1x),a\}})\) to derive a 12-LNDE-coloring of \(G\), a contradiction. If \(d_G(u_1)\geq 3\), then color \(uu_1\) with a color \(a\in C\setminus(C_\phi(u_1)\cup{R(u_1)}\cup{\{\phi(vv_1)\}})\) and color \(uv\) with a color \(b\in C\setminus(C_\phi(v_1)\cup{C_\phi(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 \(uu_1\) with a color \(a\in{C\setminus(C_\phi(x)\cup{C_\phi(v)})}\) and color \(uv\) with a color \(b\in{C\setminus(C_\phi(v)\cup R(v)\cup{\{\phi(u_1x),a\}})}\) to derive a 12-LNDE-coloring of \(G\), a contradiction. If \(d_G(u_1)\geq 3\), then color \(uu_1\) with a color \(a\in{C\setminus(C_\phi(u_1)\cup{R(u_1)\cup{C_\phi(v)}})}\) and color \(uv\) with a color \(b\in C\setminus(C_\phi(v)\cup R(v)\cup C_\phi(u_1)\cup {\{a\}})\). Since \(|C\setminus(C_\phi(u_1)\cup{R(u_1)\cup{C_\phi(v)}})|\geq 12-4-4-3=1\) and \(|C\setminus(C_\phi(v)\cup R(v)\cup C_\phi(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-\{uv\}\) has a 12-LNDE-coloring \(\phi\) using the color set \(C\). Suppose that \(\phi(uu_i)=i\) and \(\phi(vv_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_\phi(v_1)\), \(d_G(v_i)\geq d_G(v)\) and \(d_G(u_i)\geq d_G(u)\). We recolor \(vv_1\) with a color \(x\in C\setminus(\{1,2\}\cup F(v_1))\). If \(x\in C_\phi(v_2)\), then we color \(uv\) with a color \(y\in C\setminus(\{1,2\}\cup{C_{\phi}(v_{2})})\) to derive a 12-LNDE-coloring of \(G\), a contradiction. If \(x\notin C_\phi(v_2)\), then we color \(uv\) with a color \(y\in C\setminus \{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 \(uv\) with a color \(y\in C\setminus(C_{\phi}(u)\cup R(u)\cup C_{\phi}(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 \(\phi\) using the color set \(C\). Since \(|C\setminus(C_\phi(u_2)\cup R(u_2)\cup C_\phi(v))|\geq 12-4-4-3=1\), we can color \(uu_2\) with a color \(b_1\in C\setminus(C_\phi(u_2)\cup R(u_2)\cup C_\phi(v))\). Since \(|C\setminus(C_\phi(u_1)\cup R(u_1)\cup C_\phi(u_2)\cup \{b_1\})|\geq 12-3-3-4-1=1\), we can color \(uu_1\) with a color \(b_2 \in C\setminus(C_\phi(u_1)\cup R(u_1)\cup C_\phi(u_2)\cup \{b_1\})\). Since \(|C\setminus(C_\phi(v)\cup R(v)\cup C_\phi(u_1)\cup \{b_1,b_2\})|\geq 12-3-3-3-2=1\), we can color \(uv\) with a color \(b_3 \in C\setminus(C_\phi(v)\cup R(v)\cup C_\phi(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-\{uv\}\) has a 12-LNDE-coloring \(\phi\) using the color set \(C\). First, suppose that \(C_\phi(u)\subseteq C_\phi(v)\). By Lemma 2.3, \(|F(u_1)|\leq (d_G(u_1)-1)(7-d_G(u_1))=8\). We recolor \(uu_1\) with a color \(x\in C\setminus(C_\phi(v)\cup F(u_1))\). Note that \(\phi(uu_2)\notin C_\phi(u_1)\). If \(x\in C_\phi(u_2)\), we can color \(uv\) with a color \(y\in C\setminus(C_\phi(v)\cup R(v)\cup{C_{\phi}(u_{2})})\) to derive a 12-LNDE-coloring of \(G\), a contradiction. If \(x\notin C_\phi(u_2)\), then we can color \(uv\) with a color \(y\in C\setminus (C_\phi(v)\cup R(v)\cup \{x\})\) to derive a 12-LNDE-coloring of \(G\), a contradiction. Then suppose that \(C_\phi(u)\varsubsetneq C_\phi(v)\). Note that \(R(u)=\emptyset\). By Lemma 2.2, we can color \(uv\) with a color \(b\in C\setminus(C_{\phi}(u)\cup R(u)\cup C_{\phi}(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 \(\phi\) 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 \(uu_1\) with a color \(b_1\in C\setminus(C_\phi(u_1)\cup R(u_1)\cup C_\phi(u_2))\), \(uu_2\) with a color \(b_2\in C\setminus(C_\phi(u_2)\cup R(u_2)\cup C_\phi(u_3)\cup \{b_1\})\), \(uu_3\) with a color \(b_3\in C\setminus(C_\phi(u_3)\cup R(u_3)\cup C_\phi(v)\cup \{b_1,b_2\})\), and \(uv\) with a color \(b_4\in C\setminus(C_\phi(v)\cup R(v)\cup C_\phi(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-\{uv\}\) has a 12-LNDE-coloring \(\phi\) using the color set \(C\). First, suppose that \(C_\phi(u)=C_\phi(v)\). By Lemma 2.3, \(|F(u_1)|\leq (d_G(u_1)-1)(7-d_G(u_1))=8\). We recolor \(uu_{1}\) with a color \(x\in C\setminus(C_\phi(v)\cup{F(u_{1})})\). Set \(C(u)=(C_\phi(u)\cup \{x\})\setminus \{\phi(uu_1)\}\). If \(C(u) \subseteq C_\phi(u_i)\), then let \(\bar{R}(u_i)=C_\phi(u_i)\setminus C(u)\); otherwise, let \(\bar{R}(u_i)=\emptyset\). then \(C(u)\subseteq C_\phi(u_i)\), so \(|\bar{R}(u_i)|\leq 2\). Then we color \(uv\) with a color \(y\in C\setminus(C_\phi(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_\phi(u)\neq C_\phi(v)\). Then \(R(u)=\emptyset\) and \(R(v)=\emptyset\). By Lemma 2.2, we can color \(uv\) with a color \(y\in C\setminus(C_\phi(u)\cup R(u)\cup C_\phi(v)\cup R(v))\) to derive a 12-LNDE-coloring of \(G\), a contradiction. ◻
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 \(\phi\) using the color set \(C\). Then \(|R(v_3)|\leq 1\). We can color \(v_{1}v_{2}\) with a color \(a\in C\setminus(C_{\phi}(v_{1})\cup{R(v_{1})}\cup{C_{\phi}(v_{3})})\), color \(v_{4}v_{5}\) with a color \(b\in C\setminus(C_{\phi}(v_{5})\cup{R(v_{5})}\cup{C_{\phi}(v_{3})})\), color \(v_{2}v_{3}\) with a color \(c\in C\setminus(C_{\phi}(v_{3})\cup{R(v_{3})}\cup{C_{\phi}(v_{1})}\cup{\{a,b\}})\), and color \(v_{3}v_{4}\) with a color \(d\in C\setminus(C_{\phi}(v_{3})\cup{R(v_{3})}\cup{C_{\phi}(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 \(\phi\) using the color set \(C\). Let \(\phi(v_3u_i)=i\) (\(i\in \{1,2,3\}\)), \(a\in C_{\phi}(u_{1})\setminus C_{\phi}(v_{3})\) and \(b\in C_{\phi}(u_{2})\setminus C_{\phi}(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_{\phi}(v_{1})\setminus C_{\phi}(v_{5})\) and \(j\in C_{\phi}(v_{5})\setminus C_{\phi}(v_{1})\).
Subcase 2.1. \(i,j\notin\{1,2,\cdots,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\setminus(C_{\phi}(v_{1})\cup{R(v_{1})}\cup{\{1,2,3,j\}})\), and color \(v_{4}v_{5}\) with a color \(d\in C\setminus(C_{\phi}(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,\cdots,5\}\) and \(j\notin\{1,2,\cdots,5\}\).
We color \(v_{2}v_{3}\) with \(j\), color \(v_{1}v_{2}\) with a color \(a_1\in C\setminus(C_{\phi}(v_{1})\cup{R(v_{1})}\cup{\{1,2,3,j\}})\), color \(v_{4}v_{5}\) with a color \(a_2\in C\setminus(C_{\phi}(v_{5})\cup{R(v_{5})}\cup{\{1,2,3,i\}})\), and color \(v_{3}v_{4}\) with a color \(a_3\in C\setminus(C_{\phi}(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,\cdots,5\}\).
Note that \(i\in C_\phi(v_1)\cap \{1,2,\cdots,5\}\). We color \(v_{1}v_{2}\) with a color \(a_1\in C\setminus(C_{\phi}(v_{1})\cup{R(v_{1})}\cup{\{1,2,3,j\}})\), color \(v_{4}v_{5}\) with a color \(a_2\in C\setminus(C_{\phi}(v_{5})\cup{R(v_{5})}\cup{\{1,2,3,i\}})\), color \(v_{3}v_{4}\) with a color \(a_3\in C\setminus(C_{\phi}(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\setminus(C_{\phi}(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_{\phi}^{*}(u_{i})=C_{\phi}(u_{i})\) when \(d_{G}(u_{i})=3\), and \(C_{\phi}^{*}(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 \(\phi\) using color set \(C\). Hence \(R(u_i)=\emptyset\). We color \(v_{3}v_{4}\) with a color \(i\in C\setminus(C_{\phi}^{*}(u_{1})\cup{C_{\phi}^{*}(u_{2})}\cup{C_{\phi}^{*}(u_{3})}\cup{C_{\phi}(v_{5})})\) and color \(v_{2}v_{3}\) with a color \(j\in C\setminus(C_{\phi}(v_{1})\cup{\{i\}})\). Note that \(i\notin C_\phi(u_i)\) when \(d_G(u_i)=3\). So there exist a color \(a_i\in C_\phi(u_i)\setminus \{i,j\}\) for any \(i\in \{1,2,3\}\). Then we color \(v_{1}v_{2}\) with a color \(a\in C\setminus(C_{\phi}(v_{1})\cup{R(v_{1})}\cup{\{i,j\}})\), color \(v_{4}v_{5}\) with a color \(b\in C\setminus(C_{\phi}(v_{5})\cup{R(v_{5})}\cup{\{i,j\}})\), color \(v_{3}u_{1}\) with a color \(c_{1}\in C\setminus(C_{\phi}(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\setminus(C_{\phi}(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\setminus(C_{\phi}(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 \(\phi\) 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\setminus(C_{\phi}^{*}(u_{2})\cup{C_{\phi}^{*}(u_{3})}\cup{C_{\phi}(v_{1})})\) and color \(v_3v_4\) with a color \(j\in C\setminus(C_{\phi}(v_{5})\cup{\{i\}})\). Note that \(i\notin C_\phi(u_i)\) when \(d_G(u_i)=3\) for each \(i\in \{2,3\}\). So there exists a color \(a_i\in C_\phi(u_i)\setminus \{i,j\}\). Color \(v_{1}v_{2}\) with a color \(a\in C\setminus(C_{\phi}(v_{1})\cup{R(v_{1})}\cup{\{i,j\}})\), color \(v_{4}v_{5}\) with a color \(b\in C\setminus(C_{\phi}(v_{5})\cup{R(v_{5})}\cup{\{i,j\}})\), color \(u_1u'_1\) with a color \(c\in C\setminus(C_\phi(u'_1)\cup{R(u'_1)}\cup \{i,j\})\), color \(v_{3}u_{1}\) with a color \(c_{1}\in{C\setminus(C_{\phi}(u'_{1})\cup{\{a_2,a_3,c,a,b,i,j\}})}\), color \(v_{3}u_{2}\) with a color \(c_{2}\in C\setminus(C_{\phi}(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\setminus(C_{\phi}(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 \(\phi\) using the color set \(C\). Since \(v_1v_5\in E(G')\), there exists a color \(i\in C_\phi(v_1)\setminus C_\phi(v_5)\) and \(j\in C_\phi(v_5)\setminus C_\phi(v_1)\). Note that \(|R(v_1)|\leq 3\) and \(|R(v_5)|\leq 3\). Color \(v_2v_3\) with a color \(j\) and color \(v_3v_4\) with a color \(i\).
Suppose that \(d_G(u_3)=4\). Then there exists a color \(x\in{C_\phi(u_3)\setminus \{i,j\}}\), say \(x=1\). Note that \(R(u_3)=\emptyset\) by Claim 1. We color \(u_1u'_1\) with a color \(a_1\in{C\setminus(C_\phi(u'_1))\cup{R(u'_1)}\cup{}\{i,j\}}\), color \(u_2u'_2\) with a color \(a_2\in C\setminus(C_\phi(u'_2)\cup{R(u'_2)}\cup{\{i,j\}})\), color \(v_3u_1\) with a color \(b_1\in C\setminus(C_\phi(u'_1)\cup{\{a_1,a_2,1,i,j\}})\), color \(v_3u_2\) with a color \(b_2\in C\setminus(C_\phi(u'_2)\cup{\{a_1,a_2,1,i,j,b_1\}})\), color \(v_3u_3\) with a color \(b_3\in C\setminus(C_\phi(u_3)\cup R(u_3)\cup{\{a_1,a_2,i,j,b_1,b_2\}})\), color \(v_1v_2\) with a color \(a\in C\setminus(C_\phi(v_1)\cup{R(v_1)}\cup{\{b_1,b_2,b_3,j\}})\), and color \(v_4v_5\) with a color \(b\in C\setminus(C_\phi(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 \(\phi(u_3u'_3)=1\) and \(\phi(u_3u''_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_\phi(u'_3)\). We recolor \(u_3u'_3\) with a color \(x\in C\setminus(F(u'_3)\cup{}\{i,j\})\), color \(u_1u'_1\) with a color \(a_1\in C\setminus(C_\phi(u'_1)\cup{R(u'_1)}\cup{\{i,j\}})\), color \(u_2u'_2\) with a color \(a_2\in C\setminus(C_\phi(u'_2)\cup{R(u'_2)}\cup{\{i,j\}})\), color \(v_3u_3\) with a color \(b_3\in C\setminus(C_\phi(u''_3)\cup{\{i,j,x,a_1,a_2\}})\), color \(v_3u_1\) with a color \(b_1\in C\setminus(C_\phi(u'_1)\cup{\{a_1,a_2,x,i,j,b_3\}})\), color \(v_3u_2\) with a color \(b_2\in C\setminus(C_\phi(u'_2)\cup{\{a_1,a_2,x,i,j,b_1,b_3\}})\), color \(v_1v_2\) with a color \(a\in C\setminus(C_\phi(v_1)\cup{R(v_1)}\cup{\{b_1,b_2,b_3,j\}})\), and color \(v_4v_5\) with a color \(b\in C\setminus(C_\phi(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 \(\phi\) using the color set \(C\). Since \(v_1v_5\in{E(G')}\), there exists a color \(i\in C_\phi(v_1)\setminus C_\phi(v_5)\) and \(j\in{C_\phi(v_5)\setminus C_\phi(v_1)}\). Note that \(|R(v_1)|\leq 3\) and \(|R(v_5)|\leq 3\). We color \(v_2v_3\) with \(j\), color \(v_3v_4\) with \(i\), color \(u_iu'_i\) with a color \(a_i\in C\setminus(C_\phi(u'_i)\cup{R(u'_i)}\cup{\{i,j\}})\) for each \(i\in \{1,2,3\}\), color \(v_3u_1\) with a color \(b_1\in C\setminus(C_\phi(u'_1)\cup{\{a_1,a_2,a_3,i,j\}})\), color \(v_3u_2\) with a color \(b_2\in C\setminus(C_\phi(u'_2)\cup{\{a_1,a_2,a_3,i,j,b_1\}})\), color \(v_3u_3\) with a color \(b_3\in C\setminus(C_\phi(u'_3)\cup{\{a_1,a_2,a_3,i,j,b_1,b_2\}})\), color \(v_1v_2\) with a color \(a\in C\setminus(C_\phi(v_1)\cup{R(v_1)}\cup{\{b_1,b_2,b_3,j\}})\), and color \(v_4v_5\) with a color \(b\in C\setminus(C_\phi(v_5)\cup{R(v_5)}\cup{\{b_1,b_2,b_3,i\}})\) to derive a 12-LNDE-coloring of \(G\), a contradiction. ◻
Proof. Assume to the contrary that such a path \(P_3=uvw\) exists. By Claim 1, \(uw\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,\cdots,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 \(\phi\) using the color set \(C\). Let \(a_1\in C_\phi(u)\), \(a_2\in C_\phi(w)\), \(a_{i+2}\in C_\phi(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_\phi(v'_i)\) when \(d_G(v_i)=2\) with the second neighbor \(v'_i\) other than \(v\), and \(F^*(v_i)=C_\phi(v_i)\cup R(v_i)=C_\phi(v_i)\) when \(3\leq d_G(v_i)\leq 4\). Then we can color \(vv_i\) with a color in \(C\setminus F^*(v_i)\) such that \(v_i\) and its neighbors are exclusive. We color \(vv_1\) with a color \(b_1\in C\setminus(F^*(v_1)\cup{\{a_1,a_2,a_4,a_5\}})\), color \(vv_2\) with a color \(b_2\in C\setminus(F^*(v_2)\cup{\{a_1,a_2,a_3,a_5,b_1\}})\), color \(vv_3\) with a color \(b_3\in C\setminus(F^*(v_3)\cup{\{a_1,a_2,a_3,a_4,b_1,b_2\}})\), color \(uv\) with a color \(b_4\in C\setminus(C_\phi(u)\cup R(u)\cup{\{a_2,a_3,a_4,a_5,b_1,b_2,b_3\}})\), and color \(wv\) with a color \(b_5\in C\setminus(C_\phi(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-\{uv,vw\}\) has a 12-LNDE-coloring \(\phi\) using the color set \(C\). Then \(|R(v)|\leq 2\). Without loss of generality, suppose that \(\phi(vv_j)=j\) for \(j\in \{1,2,3\}\), \(\phi(uu_i)=a_i\) for \(i\in \{1,2\}\), and \(\phi(ww_l)=b_l\) for \(l\in \{1,\cdots,k-1\}\).
Subcase 2.1. \(C_\phi(u)\subseteq C_\phi(v)\), \(C_\phi(w)\subseteq C_\phi(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 \(uu_1\) with a color \(x\in C\setminus(F(u_1)\cup{C_\phi(v)})\), recolor \(ww_1\) with a color \(y\in C\setminus(F(w_1)\cup{C_\phi(v)})\). Note that \(a_2\notin C_\phi(u_1)\). So \(u\) and \(u_1\) are exclusive. Similarly, \(w\) and \(w_1\) are exclusive. If \(x\notin C_\phi(u_2)\), then we color \(uv\) with a color \(c_1\in C\setminus(C_\phi(v)\cup{R(v)}\cup{\{x,y\}})\); otherwise, we color \(uv\) with a color \(c_1\in C\setminus(C_\phi(v)\cup{R(v)}\cup{C_\phi(u_2)}\cup{\{y\}})\). If \(y\notin C_\phi(w_2)\), then we color \(wv\) with a color \(c_2\in C\setminus(C_\phi(v)\cup{R(v)}\cup{\{x,y,c_1\}})\); otherwise, we color \(wv\) with a color \(c_2\in C\setminus(C_\phi(v)\cup{R(v)}\cup{C_\phi(w_2)}\cup{\{x,c_1\}})\). Note that \(b_2\in C_\phi(w_2)\cap C_\phi(w)\subseteq C_\phi(v)\). Then \(|C\setminus(C_\phi(v)\cup R(v)\cup C_\phi(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 \(uu_1\) with a color \(x\in C\setminus(F(u_1)\cup{C_\phi(v)})\) and recolor \(ww_1\) with a color \(y\in C\setminus(F(w_1)\cup{C_\phi(v)})\). For \(i\in \{2,3\}\), if \(\{y,b_2,b_3\}\subseteq C_\phi(w_i)\), let \(\bar{R}(w_i)=C_\phi(w_i)\setminus \{y,b_2,b_3\}\); otherwise, let \(\bar{R}(w_i)=\emptyset\). Note that \(C_\phi(w)=C_\phi(v)\). We color \(wv\) with a color \(c_1\in C\setminus(C_\phi(v)\cup{R(v)}\cup{\bar{R}(w_2)}\cup{\bar{R}(w_3)}\cup{\{x,y\}})\). If \(x\notin C_\phi(u_2)\), we color \(uv\) with a color \(c_2\in C\setminus(C_\phi(v)\cup{R(v)}\cup{\{x,c_1,y\}})\); otherwise, we color \(uv\) with a color \(c_2\in C\setminus(C_\phi(v)\cup{R(v)}\cup{C_\phi(u_2)}\cup{\{c_1,y\}})\). Note that \(a_2\in C_\phi(u_2)\cap C_\phi(u)\subseteq C_\phi(v)\). Then \(|C\setminus(C_\phi(v)\cup{R(v)}\cup{C_\phi(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_\phi(u)\subseteq C_\phi(v)\), \(C_\phi(w)\varsubsetneq C_\phi(v)\).
Let \(\alpha \in C_\phi(w)\setminus C_\phi(v)\). By Lemma 2.3, \(|F(u_1)|\leq 8\). We recolor \(uu_1\) with a color \(x\in C\setminus(F(u_1)\cup{C_\phi(v)})\). If \(x\notin C_\phi(u_2)\), then we color \(uv\) with a color \(c_1\in C\setminus(C_\phi(v)\cup{R(v)}\cup{\{x,\alpha\}})\); otherwise, we color \(uv\) with a color \(c_1\in C\setminus(C_\phi(v)\cup{R(v)}\cup{C_\phi(u_2)}\cup{\{\alpha\}})\). Then we color \(wv\) with a color \(c_2\in C\setminus(C_\phi(v)\cup{R(v)}\cup{C_\phi(w)}\cup{\{x,c_1\}})\) to derive a 12-LNDE-coloring of \(G\), a contradiction.
Subcase 2.3. \(C_\phi(u)\varsubsetneq C_\phi(v)\), \(C_\phi(w)\subseteq C_\phi(v)\).
If \(d_G(w)=3\), then the proof is the same as Subcase 2.2. So suppose that \(d_G(w)=4\). Let \(\alpha \in C_\phi(u)\setminus C_\phi(v)\). By Lemma 2.3, \(|F(w_1)|\leq 8\). We recolor \(ww_1\) with a color \(y\in C\setminus(F(w_1)\cup{C_\phi(v)})\). For \(i\in \{2,3\}\), if \(\{y,b_2,b_3\}\subseteq C_\phi(w_i)\), then let \(\bar{R}(w_i)=C_\phi(w_i)\setminus \{y,b_2,b_3\}\), otherwise, let \(\bar{R}(w_i)=\emptyset\). Note that \(C_\phi(w)=C_\phi(v)\). We color \(wv\) with a color \(c_1\in C\setminus(C_\phi(v)\cup{R(v)}\cup{\bar{R}(w_2)}\cup{\bar{R}(w_3)}\cup{\{\alpha,y\}})\), and color \(uv\) with a color \(c_2\in C\setminus(C_\phi(u)\cup C_\phi(v)\cup R(v)\cup \{c_1,y\})\) to derive a 12-LNDE-coloring of \(G\), a contradiction.
Subcase 2.4. \(C_\phi(u)\varsubsetneq C_\phi(v)\), \(C_\phi(w)\varsubsetneq C_\phi(v)\).
Let \(\alpha \in C_\phi(u)\setminus C_\phi(v)\) and \(\beta \in C_\phi(w)\setminus C_\phi(v)\). We color \(uv\) with a color \(c_1\in C\setminus(C_\phi(v)\cup{R(v)}\cup{C_\phi(u)}\cup{\{\beta\}})\), and color \(wv\) with a color \(c_2\in C\setminus(C_\phi(v)\cup{R(v)}\cup{C_\phi(w)}\cup{\{\alpha,c_1\}})\) to derive a 12-LNDE-coloring of \(G\), a contradiction. ◻
Proof. Assume to the contrary that such a path \(P_3=uvw\) exists. By Claim 1, \(uw\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-\{uv,vw\}\) has a 12-LNDE-coloring \(\phi\) using the color set \(C\).
Case 1. \(C_\phi(u)=C_\phi(v)=C_\phi(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 \(vv_1\) with a color \(x\in C\setminus(F(v_1)\cup C_\phi(v))\). Then there exists a color \(a_i\in C_\phi(v_i)\setminus ((C_\phi(v)-\{\phi(vv_1)\})\cup \{x\})\) for each \(i\in \{2,3\}\). Color \(uv\) with a color \(b_1\in C\setminus(C_\phi(u)\cup R(u)\cup \{x,a_2,a_3\})\), and color \(wv\) with a color \(b_2\in C\setminus(C_\phi(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 \(vv_2\) with a color \(x\in C\setminus(C_\phi(v'_2)\cup C_\phi(v))\). Then there exists a color \(a_i\in C_\phi(v_i)\setminus ((C_\phi(v)-\{\phi(vv_2)\})\cup \{x\})\) for each \(i\in \{1,3\}\). We color \(uv\) with a color \(b_1\in C\setminus(C_\phi(u)\cup R(u)\cup C_\phi(v_2)\cup \{x,a_1,a_3\})\), and color \(wv\) with a color \(b_2\in C\setminus(C_\phi(w)\cup R(w)\cup C_\phi(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 \(vv_2\) with a color \(x\in C\setminus(C_\phi(v'_2)\cup C_\phi(v)\cup C_\phi(v_3))\). Then there exists a color \(a_1\in C_\phi(v_1)\setminus (C_\phi(v)\cup \{x\})\). We color \(uv\) with a color \(b_1\in C\setminus(C_\phi(u)\cup R(u)\cup \{a_1,\phi(v_2v'_2),\phi(v_3v'_3),x\})\), and color \(wv\) with a color \(b_2\in C\setminus(C_\phi(w)\cup R(w)\cup \{a_1,\phi(v_2v'_2),\phi(v_3v'_3),x,b_1\})\) to derive a 12-LNDE-coloring of \(G\), a contradiction.
Case 2. \(C_\phi(u)\neq C_\phi(v)\), \(C_\phi(w)= C_\phi(v)\).
Let \(\alpha \in C_\phi(u)\setminus C_\phi(v)\). By Lemma 2.3, \(|F(w_1)|\leq 8\). Let \(\phi(ww_i)=b_i\) for \(i\in \{1,2,3\}\). We recolor \(ww_1\) with a color \(y\in C\setminus(F(w_1)\cup{C_\phi(v)})\). For each \(i\in \{2,3\}\), if \(\{y,b_2,b_3\} \subseteq C_\phi(w_i)\), let \(\bar{R}(w_i)=C_\phi(w_i)\setminus C_\phi(w)\); otherwise, let \(\bar{R}(w_i)=\emptyset\). We color \(wv\) with a color \(a_1\in C\setminus(C_\phi(v)\cup{R(v)}\cup{\bar{R}(w_2)}\cup{\bar{R}(w_3)}\cup{\{\alpha,y\}})\), and color \(uv\) with a color \(a_2\in C\setminus(C_\phi(u)\cup R(u)\cup C_\phi(v)\cup R(v)\cup \{a_1,y\})\) to derive a 12-LNDE-coloring of \(G\), a contradiction.
Case 3. \(C_\phi(u)\neq C_\phi(v)\), \(C_\phi(w)\neq C_\phi(v)\).
Let \(\alpha\in C_\phi(u)\setminus C_\phi(v)\) and \(\beta\in C_\phi(w)\setminus C_\phi(v)\). Then we color \(wv\) with a color \(a_1\in C\setminus(C_\phi(v)\cup R(v)\cup C_\phi(w)\cup R(w)\cup \{\alpha\})\), and color \(uv\) with a color \(a_2\in C\setminus(C_\phi(v)\cup R(v)\cup C_\phi(u)\cup R(u)\cup \{a_1,\beta\})\) to derive a 12-LNDE-coloring of \(G\), a contradiction. ◻
Proof. Assume to the contrary that \(n_{4^-}(v)\geq 4\). Then \(n_5(v)\leq 1\). Let \(v_1,v_2,\cdots,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-\{vv_1\}\) has a 12-LNDE-coloring \(\phi\) using the color set \(C\).
Suppose that \(C_\phi(v_1)\subseteq C_\phi(v)\). Note that \(n_5(v)=1\) and \(|C_\phi(v_1)|=2\). Then \(\{\phi(vv_2),\phi(vv_3),\) \(\phi(vv_4)\}\cap C_\phi(v_1)\neq \emptyset\), say \(\phi(vv_2)\in C_\phi(v_1)\). We recolor \(vv_2\) with a color \(x\in C\setminus(C_\phi(v'_2)\cup C_\phi(v)\cup R(v))\). Let \(\alpha \in C_\phi(v_5)\setminus ((C_\phi(v)-\{\phi(vv_2)\})\cup \{x\})\). Then we color \(vv_1\) with a color \(y\in C\setminus(C_\phi(v)\cup R(v)\cup C_\phi(v_1) \cup \{x,\alpha\})\) to derive a 12-LNDE-coloring of \(G\), a contradiction. If \(C_\phi(v_1)\varsubsetneq C_\phi(v)\). Then we color \(vv_1\) with a color \(y\in C\setminus(C_\phi(v_1)\cup R(v_1)\cup C_\phi(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 \(\phi\) using the color set \(C\). Let \(\phi(v_iv'_i)=a_i\) for \(i\in \{2,3,4,5\}\). Then we color \(vv_4\) with a color \(b_4\in C\setminus(C_\phi(v'_4)\cup C_\phi(v_1)\cup \{a_2,a_3,a_5\})\), color \(vv_5\) with a color \(b_5\in C\setminus(C_\phi(v'_5)\cup C_\phi(v_1)\cup \{a_2,a_3,a_4,b_4\})\), color \(vv_3\) with a color \(b_3\in C\setminus(C_\phi(v'_3)\cup C_\phi(v_1)\cup \{a_4,a_5,b_4,b_5\})\), color \(vv_2\) with a color \(b_2\in C\setminus(C_\phi(v'_2)\cup \{a_4,a_5,b_3,b_4,b_5\})\), and color \(vv_1\) with a color \(b_1\in C\setminus(C_\phi(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'_2v'_3\notin E(G)\). Let \(G'\)=\(G-\{v,v_2,v_3,v_4,v_5\}+\{v'_2v'_3\}\). By the minimality of \(G\), \(G'\) has a 12-LNDE-coloring \(\phi\) using the color set \(C\). Let \(\phi(v'_2v'_3)=a_1\). Note that \(a_1\in C_\phi(v'_2)\cap C_\phi(v'_3)\). We color \(v_2v'_2\) and \(v_3v'_3\) with the color \(a_1\). Then we color \(v_4v'_4\) with a color \(a_4\in C\setminus(C_\phi(v'_4)\cup R(v'_4)\cup \{a_1\})\), color \(v_5v'_5\) with a color \(a_5\in C\setminus(C_\phi(v'_5)\cup R(v'_5)\cup \{a_1\})\), color \(vv_4\) with a color \(b_4\in C\setminus(C_\phi(v'_4)\cup C_\phi(v_1)\cup \{a_1,a_5\})\), color \(vv_5\) with a color \(b_5\in C\setminus(C_\phi(v'_5)\cup C_\phi(v_1)\cup \{a_1,a_4,b_4\})\), color \(vv_3\) with a color \(b_3\in C\setminus(C_\phi(v'_3)\cup C_\phi(v_1)\cup \{a_4,a_5,b_4,b_5\})\), color \(vv_2\) with a color \(b_2\in C\setminus(C_\phi(v'_2)\cup \{a_4,a_5,b_3,b_4,b_5\})\), and color \(vv_1\) with a color \(b_1\in C\setminus(C_\phi(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. ◻
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 \(\phi\) using the color set \(C\). Then \(|R(v_i)|\leq 2\). Suppose that \(C_\phi(v_1)\cap C_\phi(v_2)\neq \emptyset\). Then we color \(vv_2\) with a color \(b\in C\setminus(C_\phi(v_2)\cup R(v_2)\cup C_\phi(v_3))\), color \(vv_3\) with a color \(c\in C\setminus(C_\phi(v_3)\cup R(v_3)\cup C_\phi(v_1)\cup \{b\})\), and color \(vv_1\) with a color \(a\in C\setminus(C_\phi(v_1)\cup R(v_1)\cup C_\phi(v_2)\cup \{b,c\})\) to derive a 12-LNDE-coloring of \(G\), a contradiction. So suppose that \(C_\phi(v_1)\cap C_\phi(v_2)=\emptyset\). By symmetry, \(C_\phi(v_2)\cap C_\phi(v_3)=\emptyset\) and \(C_\phi(v_1)\cap C_\phi(v_3)=\emptyset\). That is \(C_\phi(v_1)=\{a_1,a_2,a_3,a_4\}\), \(C_\phi(v_2)=\{a_5,a_6,a_7,a_8\}\) and \(C_\phi(v_3)=\{a_9,a_{10},a_{11},a_{12}\}\). Obviously \(R(v_1)\cap C_\phi(v_2)\neq \emptyset\) or \(R(v_1)\cap C_\phi(v_3)\neq \emptyset\), say \(R(v_1)\cap C_\phi(v_2)\neq \emptyset\). Then we color \(vv_2\) with a color \(b\in C\setminus(C_\phi(v_2)\cup R(v_2)\cup C_\phi(v_3))\), color \(vv_3\) with a color \(c\in C\setminus(C_\phi(v_3)\cup R(v_3)\cup C_\phi(v_1)\cup \{b\})\), and color \(vv_1\) with a color \(a\in C\setminus(C_\phi(v_1)\cup R(v_1)\cup C_\phi(v_2)\cup \{b,c\})\) to derive a 12-LNDE-coloring of \(G\), a contradiction. ◻
Proof. Assume to the contrary that \(n_{4^-}(v)\geq 3\) then \(n_5(v)\leq 2\). Let \(v_1,v_2,\cdots,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-\{vv_1\}\) has a 12-LNDE-coloring \(\phi\) using the color set \(C\).
Suppose that \(C_\phi(v_1)\subseteq C_\phi(v)\). Note that \(n_5(v)\leq 2\) and \(|C_\phi(v_1)|=3\). Then \(\{\phi(vv_2),\phi(vv_3)\}\) \(\cap C_\phi(v_1)\neq \emptyset\), say \(\phi(vv_2)\in C_\phi(v_1)\). We recolor \(vv_2\) with a color \(x\in C\setminus(C_\phi(v'_2)\cup R(v)\cup C_\phi(v))\). Let \(\alpha_i\in C_\phi(v_i)\setminus ((C_\phi(v)-\{\phi(vv_2)\})\cup \{x\})\), when \(d_G(v_i)=5\). If \(d_G(v_4)=5\), then we color \(vv_1\) with a color \(y\in C\setminus(C_\phi(v)\cup \{x,\alpha_4,\alpha_5,\phi(v_3v'_3),\phi(v_2v'_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 \(vv_1\) with a color \(y\in C\setminus (C_\phi(v)\cup \{x,\alpha_5,\phi(v_2v'_2),\phi(v_3v'_3),\phi(v_4v'_4)\})\) to derive a 12-LNDE-coloring of \(G\), a contradiction. If \(C_\phi(v_1)\varsubsetneq C_\phi(v)\). We color \(vv_1\) with a color \(y\in C\setminus(C_\phi(v_1)\cup R(v_1)\cup C_\phi(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 \(\phi\) using the color set \(C\). Let \(\phi(v_iv'_i)=a_i\) for \(i\in \{2,3,4,5\}\). Then we color \(vv_2\) with a color \(b_2\in C\setminus(C_\phi(v'_2)\cup C_\phi(v_1)\cup \{a_4,a_5\})\), color \(vv_3\) with a color \(b_3\in C\setminus(C_\phi(v'_3)\cup C_\phi(v_1)\cup \{a_4,a_5,b_2\})\), color \(vv_4\) with a color \(b_4\in C\setminus(C_\phi(v'_4)\cup \{a_2,a_3,a_5,b_2,b_3\})\), color \(vv_5\) with a color \(b_5\in C\setminus(C_\phi(v'_5)\cup \{a_2,a_3,a_4,b_2,b_3,b_4\})\), and color \(vv_1\) with a color \(b_1\in C\setminus(C_\phi(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_\phi(v_1)\), then \(C_\phi(v_1)\varsubsetneq C_\phi(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'_2v'_3\notin E(G)\). Let \(G'\)=\(G-\{v,v_2,v_3,v_4,v_5\}+\{v'_2v'_3\}\). By the minimality of \(G\), \(G'\) has a 12-LNDE-coloring \(\phi\) using the color set \(C\). Let \(\phi(v'_1v'_2)=a_1\). Note that \(a_1\in C_\phi(v'_2)\cap C_\phi(v'_3)\). Then we color \(v_2v'_2\) and \(v_3v'_3\) with the color \(a_1\). Now, we color \(v_4v'_4\) with a color \(a_4\in C\setminus(C_\phi(v'_4)\cup R(v'_4)\cup \{a_1\})\), color \(v_5v'_5\) with a color \(a_5\in C\setminus(C_\phi(v'_5)\cup R(v'_5)\cup \{a_1\})\), color \(vv_2\) with a color \(b_2\in C\setminus(C_\phi(v'_2)\cup C_\phi(v_1)\cup \{a_4,a_5\})\), color \(vv_3\) with a color \(b_3\in C\setminus(C_\phi(v'_3)\cup C_\phi(v_1)\cup \{a_4,a_5,b_2\})\), color \(vv_4\) with a color \(b_4\in C\setminus(C_\phi(v'_4)\cup \{a_1,a_5,b_2,b_3\})\), color \(vv_5\) with a color \(b_5\in C\setminus(C_\phi(v'_5)\cup \{a_1,a_4,b_2,b_3,b_4\})\), and color \(vv_1\) with a color \(b_1\in C\setminus(C_\phi(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_\phi(v_1)\), then \(C_\phi(v_1)\varsubsetneq C_\phi(v)\). Hence, the obtained coloring is the 12-LNDE-coloring of \(G\), a contradiction. ◻
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 \(\phi\) using the color set \(C\). Then \(|R(v_i)|\leq 1\). Note that \(|C_\phi(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_\phi(v_i)\cap C_\phi(v_j)\neq \emptyset\), say \(C_\phi(v_1)\cap C_\phi(v_2)\neq \emptyset\). Now, we color \(vv_2\) with a color \(b\in C\setminus(C_\phi(v_2)\cup R(v_2)\cup C_\phi(v_3))\), color \(vv_3\) with a color \(c\in C\setminus(C_\phi(v_3)\cup R(v_3)\cup C_\phi(v_4)\cup \{b\})\), color \(vv_4\) with a color \(d\in C\setminus(C_\phi(v_4)\cup R(v_4)\cup C_\phi(v_1)\cup \{b,c\})\), and color \(vv_1\) with a color \(a\in C\setminus(C_\phi(v_1)\cup R(v_1)\cup C_\phi(v_2)\cup \{b,c,d\})\). Note that \(C_\phi(v_1)\cap C_\phi(v_2)\neq \phi\), then \(|C\setminus (C_\phi(v_1)\cup R(v_1)\cup C_\phi(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. ◻
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 \(\phi\) using the color set \(C\). Then \(|R(v_2)|\leq 2\). We color \(v_1v_4\) with a color \(a\in C\setminus(C_\phi(v_4)\cup R(v_4)\cup C_\phi(v_2))\), color \(v_3v_4\) with a color \(b\in C\setminus(C_\phi(v_4)\cup R(v_4)\cup C_\phi(v_2)\cup \{a\})\), color \(v_2v_3\) with a color \(c\in C\setminus(C_\phi(v_4)\cup C_\phi(v_2)\cup R(v_2)\cup \{a,b\})\), and color \(v_1v_2\) with a color \(d\in C\setminus(C_\phi(v_4)\cup C_\phi(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\cong 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_1w_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 \(\phi\) using the color set \(C\). Let \(\phi(u_iu'_i)=a_i\) and \(\phi(w_iw'_i)=b_i\) for \(i\in \{1,2,3\}\). Then we color \(v_2u_1\) and \(v_4w_1\) with a color \(\alpha\in C\setminus(C_\phi(u'_1)\cup C_\phi(w'_1))\), Color \(v_4w_2\) with a color \(c_1\in C\setminus(C_\phi(w'_2)\cup \{\alpha,b_1,b_3\})\), \(v_4w_3\) with a color \(c_2\in C\setminus(C_\phi(w'_3)\cup \{\alpha,b_1,b_2,c_1\})\), color \(v_2u_2\) with a color \(c_3\in C\setminus(C_\phi(u'_2)\cup \{\alpha,a_1,a_3,c_1,c_2\})\), color \(v_2u_3\) with a color \(c_4\in C\setminus(C_\phi(u'_3)\cup \{\alpha,a_1,a_2,c_1,c_2,c_3\})\), color \(v_1v_4\) with a color \(d_1\in C\setminus \{\alpha,c_1,c_2,c_3,c_4,b_1,b_2,b_3\}\), color \(v_3v_4\) with a color \(d_2\in C\setminus \{\alpha,c_1,c_2,c_3,c_4,b_1,b_2,b_3,d_1\}\), color \(v_1v_2\) with a color \(d_3\in C\setminus\{\alpha,c_1,c_2,c_3,c_4,a_1,a_2,a_3,d_1,d_2\}\), and color \(v_2v_3\) with a color \(d_4\in C\setminus \{\alpha,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. ◻
Proof. Assume to the contrary that such a path \(P_5=v_1v_2v_3v_4v_5\) exists. Let \(u_{1}, u_{2}, u_3\) be the neighbors of \(v_3\) not in \(P_5\). Then \(v_1v_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 \(\phi\) using the color set \(C\). Then \(|R(v_3)|\leq 1\). We color \(v_1v_2\) with a color \(a\in C\setminus(C_\phi(v_1)\cup R(v_1)\cup C_\phi(v_3))\), color \(v_4v_5\) with a color \(b\in C\setminus(C_\phi(v_5)\cup R(v_5)\cup C_\phi(v_3))\), color \(v_2v_3\) with a color \(c\in C\setminus(C_\phi(v_1)\cup C_\phi(v_3)\cup R(v_3)\cup \{a,b\})\), and color \(v_3v_4\) with a color \(d\in C\setminus(C_\phi(v_5)\cup C_\phi(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_1v_5\). By the minimality of \(G\), \(G'\) has a 12-LNDE-coloring \(\phi\) using the color set \(C\). Let \(\phi(v_1v_5)=\alpha\). We color \(v_1v_2\) and \(v_4v_5\) with the color \(\alpha\), color \(v_3u_1\) with a color \(a_1\in C\setminus(C_\phi(u'_1)\cup C_\phi(u_3)\cup \{\alpha\})\), color \(v_3u_3\) with a color \(a_3\in C\setminus(C_\phi(u_3)\cup R(u_3)\cup \{\alpha,a_1\})\), color \(v_3u_2\) with a color \(a_2\in C\setminus(C_\phi(u'_2)\cup \{\alpha,a_1,a_3\})\), color \(u_1u'_1\) with a color \(b_1\in C\setminus(C_\phi(u'_1)\cup R(u'_1)\cup \{a_1,a_2,a_3\})\), color \(u_2u'_2\) with a color \(b_2\in C\setminus(C_\phi(u'_2)\cup R(u'_2)\cup \{a_1,a_2,a_3\})\), color \(v_3v_2\) with a color \(a_4\in C\setminus(C_\phi(v_1)\cup \{\alpha,a_1,a_2,a_3,b_1,b_2\})\), and color \(v_3v_4\) with a color \(a_5\in C\setminus(C_\phi(v_5)\cup \{\alpha,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'_1u'_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_1v_5, u'_1u'_2\}\). By the minimality of \(G\), \(G'\) has a 12-LNDE-coloring \(\phi\) using the color set \(C\). Let \(\phi(v_1v_5)=\alpha\) and \(\phi(u'_1u'_2)=\beta\). We color \(v_1v_2\) and \(v_4v_5\) with the color \(\alpha\), color \(u_1u'_1\) and \(u_2u'_2\) with the color \(\beta\), color \(u_3u'_3\) with a color \(\gamma \in C\setminus(C_\phi(u'_3)\cup R(u'_3))\), color \(v_3u_1\) with a color \(a_1\in C\setminus(C_\phi(u'_1)\cup \{\alpha,\beta,\gamma\})\), color \(v_3u_2\) with a color \(a_2\in C\setminus(C_\phi(u'_2)\cup \{\alpha,\beta,\gamma,a_1\})\), color \(v_3u_3\) with a color \(a_3\in C\setminus(C_\phi(u'_3)\cup \{\alpha,\beta,\gamma,a_1,a_2\})\), color \(v_3v_2\) with a color \(a_4\in C\setminus(C_\phi(v_1)\cup \{\alpha,\beta,\gamma,a_1,a_2,a_3\})\), and color \(v_3v_4\) with a color \(a_5\in C\setminus(C_\phi(v_5)\cup \{\alpha,\beta,\gamma,a_1,a_2,a_3,a_4\})\) to derive a 12-LNDE-coloring of \(G\), a contradiction. ◻
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 \(\phi\) using the color set \(C\). Then \(R(v_1)=R(v_2)=\emptyset\). We color \(vv_1\) with a color \(a\in C\setminus(C_\phi(v_1)\cup R(v_1)\cup C_\phi(v_2))\), and color \(vv_2\) with a color \(b\in C\setminus(C_\phi(v_1)\cup C_\phi(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.
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).