2 Main Results
Lemma 2.1 Let $G$ be a simple graph with maximum degree $3$ and minimum degree $2$. If $G$ has no adjacent $\Delta$-vertices, and every vertex of degree $2$ is adjacent only to two vertices of degree $3$, then $\chi\, ''_{as}(G)=4$.
Proof By induction on orders of graphs.
Basis Step There are just two graphs that have two and four $\Delta$-vertices shown in Figure 1, since no graphs $G$ having five $\Delta$-vertices when $\Delta(G)=3$ and $\delta(G)\geq 2$. These graphs hold $\chi\, ''_{as}(G)=4$.
Induction Step Suppose that the lemma holds for graphs of smaller orders. We have a graph $G\, '=G-\{u, w, v\}+\{a, b\}$, $a$ is the vertex such that $x$ adhere with $y$, $b$ is the vertex such that $s$ adhere with $t$, where $G$ is Figure 2(a) and $G\, '$ is Figure 2(b). From $|G|>|G\, '|$ and $G\, '$ satisfies the the lemma's hypothesis, we have $\chi\, ''_{as}(G\, ')=4$ by induction hypothesis. Our goal is to show $\chi\, '' _{as}(G)=4$. Let $f$ be an AVDTC of $G\, '$ with $f(V(G\, ')\cup E(G\, ')=C=[1, 4]$.
We define a total coloring $g$ of the graph $G$ as:
$g(x)=g(y)=f(a)$, $g(xx\, ')= f(ax\, ')$, $g(ux)=f(ay\, ')$,
$g(yy\, ')=f(ay\, ')$, $g(uy)=f(ax\, ')$, $g(s)=g(t)=f(b)$, $g(ss\, ')
=f(bs\, ')$, $g(vs)=f(bt\, ')$, $g(tt\, ')=f(bt\, ')$,
$g(vt)=f(bs\, ')$. Therefore, $C(x, f)=C(y, f)$, $C(s, f)=C(t, f)$. Take $g(z)=f(z)$ for $z\in \{V(G)\cup E(G)\}\setminus
\{u, w, v, x, y, s, t, ux, uy, vs, vt, uw, wv, xx\, ', \\ yy\, ', ss\, ', tt\, '\}$. By analysis, if we accord to color $G$ in the mapping of $g$, then some situations don't satisfy a proper total coloring with four colors. Now we will use the following cases to solve it. Let $h$ be a new total coloring of the graph $G$.
Case 1 $f(a)=f(b)$.
Without loss of generality, suppose $f(a)=f(b)=1$, $f(ax\, ')=2$,
$f(ay\, ')=3$, then $g(u)=4$, $g(uw)=1$.
Case 1.1 $C(x, g)=C(y, g)=C(s, g)=C(t, g)=\{1, 2, 3\}$.
Case 1.1.1 $f(bs\, ')=2$, $f(bt\, ')=3$.
The possible case is $g(t\, ')=2$ or $4$. If $g(t\, ')=2$, we set $h(t)=4$, $h(vt)=1$, thus $h(v)=2$ and $h(wv)=4$, $h(w)=3$. If $g(t\, ')=4$, then we set $h(t)=2$ and $h(vt)=1$. Consequently,
$h(v)=4$, $h(wv)=2$ and $h(w)=3$. Next, we define $h(z)=g(z)$ for $z\in \{V(G)\cup E(G)\}\setminus \{w, v, t, vt, wv\}$. Therefore, $h$ is an AVDTC of $G$.
Case 1.1.2 $f(bs\, ')=3$, $f(bt\, ')=2$.
In this case, $g(t\, ')=3$ or $4$. If $g(t\, ')=3$, then set $h(t)=4$, $h(vt)=1$. Hence, $h(v)=3$, $h(wv)=4$, $h(w)=2$. If $g(t\, ')=4$, then set $h(t)=3$, $h(vt)=1$, which induce $h(v)=4$,
$h(wv)=3$ and $h(w)=2$. Next, we let $h(z)=g(z)$ for $z\in
\{V(G)\cup E(G)\}\setminus \{w, v, t, vt, wv\}$. So, $h$ is an AVDTC of $G$.
Case 1.2 $C(x, g)=C(y, g)=\{1, 2, 3\}$,
$C(s, g)=C(t, g)=\{1, 2, 4\}$.
Case 1.2.1 $f(bs\, ')=2$, $f(bt\, ')=4$.
We know $g(t\, ')=2$ or $3$ in this case. If $g(t\, ')=2$, then set $h(t)=3$, $h(vt)=1$. Clearly, $h(v)=2$, $h(wv)=4$, $h(vs)=3$,
$h(w)=3$. If $g(t\, ')=3$, then set $h(t)=2$, $h(vt)=1$. We can define $h(v)=4$, $h(wv)=2$, $h(vs)=3$, $h(w)=3$, and set $h(z)=g(z)$ for $z\in \{V(G)\cup E(G)\}\setminus
\{w, v, t, vs, vt, wv\}$. We can say that $h$ is an AVDTC of $G$.
Case 1.2.2 $f(bs\, ')=4$, $f(bt\, ')=2$.
Clearly, $g(t\, ')=3$ or $4$. If $g(t\, ')=3$, then set $h(t)=4$,
$h(vt)=1$, which induce $h(v)=3$, $h(wv)=4$ and $h(w)=2$. If $g(t\, ')=4$, then set $h(t)=3$, $h(vt)=1$. Consequently, we set $h(v)=4$, $h(wv)=3$, $h(w)=2$. Hence, we can define $h(z)=g(z)$ for $z\in \{V(G)\cup E(G)\}\setminus \{w, v, t, vt, wv\}$. Thereby,
$h$ is an AVDTC of $G$.
Case 1.3 $C(x, g)=C(y, g)=\{1, 2, 3\}$,
$C(s, g)=C(t, g)=\{1, 3, 4\}$.
Case 1.3.1 $f(bs\, ')=3$, $f(bt\, ')=4$.
It is not hard to see that $g(t\, ')=2$ or $3$. If $g(t\, ')=2$, then set $h(t)=3$, $h(vt)=1$, which induce $h(v)=4$, $h(wv)=3$,
$h(vs)=2$ and $h(w)=2$. If $g(t\, ')=3$, then set $h(t)=2$,
$h(vt)=1$. We will get $h(v)=3$, $h(wv)=4$, $h(vs)=2$, $h(w)=2$. We define $h(z)=g(z)$ for $z\in \{V(G)\cup E(G)\}\setminus
\{w, v, t, vs, vt, wv\}$. This total coloring of $h$ is an AVDTC of $G$.
Case 1.3.2 $f(bs\, ')=4$, $f(bt\, ')=3$.
Here, $g(t\, ')=2$ or $4$. If $g(t\, ')=2$, then set $h(t)=4$,
$h(vt)=1$, which induce $h(v)=2$, $h(wv)=4$ and $h(w)=3$. If $g(t\, ')=4$, then set $h(t)=2$, $h(vt)=1$. We define $h(v)=4$,
$h(wv)=2$, $h(w)=3$ and $h(z)=g(z)$ for $z\in \{V(G)\cup
E(G)\}\setminus \{w, v, t, vt, wv\}$. So, $h$ is an AVDTC of $G$.
Case 2 $f(a)\neq f(b)$.
Without loss of generality, we assume that $f(a)=1$, $f(b)=2$,
$f(ax\, ')=2$ and $f(ay\, ')=3$. Then $g(u)=4$, $g(uw)=1$.
Case 2.1 $C(x, g)=C(y, g)=C(s, g)=C(t, g)=\{1, 2, 3\}$.
Clearly, we can set $h(wv)=2$, $h(w)=3$, and $h(z)=g(z)$ for $z\in
\{V(G)\cup E(G)\}\setminus \{w, wv\}$. Hence, $h$ is an AVDTC of $G$.
Case 2.2 $C(x, g)=C(y, g)=\{1, 2, 3\}$,
$C(s, g)=C(t, g)=\{1, 2, 4\}$.
Case 2.2.1 $f(bs\, ')=1$, $f(bt\, ')=4$.
We know $g(t\, ')=1$ or $3$. If $g(t\, ')=1$, we set $h(t)=3$,
$h(vt)=2$, and furthermore $h(v)=1$, $h(wv)=3$, $h(w)=2$; if $g(t\, ')=3$, then set $h(t)=1$, $h(vt)=2$. We can set $h(v)=3$,
$h(wv)=1$, $h(w)=2$, and $h(z)=g(z)$ for $z\in \{V(G)\cup
E(G)\}\setminus \{w, v, t, vt, wv\}$. It means that $h$ is an AVDTC of $G$.
Case 2.2.2 $f(bs\, ')=4$, $f(bt\, ')=1$.
It is not hard to see $g(t\, ')=3$ or $4$. If $g(t\, ')=3$, we set $h(t)=4$, $h(vt)=2$, and define $h(v)=3$, $h(wv)=4$, $h(w)=2$; if $g(t\, ')=4$, we let $h(t)=3$, $h(vt)=2$. For other vertices and edges, we set $h(v)=4$, $h(wv)=3$, $h(w)=2$, and $h(z)=g(z)$ for $z\in \{V(G)\cup E(G)\}\setminus \{w, v, t, vt, wv\}$. It is obvious that $h$ is an AVDTC of $G$.
Case 2.3 $C(x, g)=C(y, g)=\{1, 2, 3\}$,
$C(s, g)=C(t, g)=\{2, 3, 4\}$.
Thereby, set $h(wv)=2$, $h(w)=3$. We define $h(z)=g(z)$ for $z\in
\{V(G)\cup E(G)\}\setminus \{w, wv\}$. Eventually, $h$ is an AVDTC of $G$.
The lemma follows from the principle of induction.
Lemma 2.2 Let $G$ be a simple graph with maximum degree $3$ and minimum degree 2. Suppose that $G$ has no adjacent $\Delta$-vertices and every vertices of degree $2$ is adjacent only to vertices of degree $3$. Replacing an edge $uv$ with a path $uwv$, where $uv\in E(G)$ and $w\not\in V(G)$, produces a new graph $H$ such that $\chi\, ''_{as}(H)\leq 5$.
Proof Let $f$ be a $k$-AVDTC of a simple graph $G$ of maximum degree $3$ with $k\geq \chi\, ''_{as}(G)$, and $C=[1, k]$ be the color set of $G$ under the coloring $f$. We show the lemma in the following cases. Let $f(uv)=\alpha$ for an edge $uv\in E(G)$, where $d _{G}(u)=2$, $d_{G} (v)=\Delta(G)=3$, $N_{G}(u)=\{x, v\}$,
$N_{G}(v)=\{u, w_1, w_2\}$. An edge $uv$ in $G$ is replaced by a path $uwv$, where $w\not\in V(G)$. We define a total coloring $h$ of $H$ as following. First, set $h(wv)=\alpha$.
Case 1 $f(x)\neq \alpha$.
Let $\{a_1\}\subseteq C \setminus C(u, f)$, then $\alpha\neq a_1$,
$h(ux)\neq a_1$. We define $h(u)=\alpha$, $h(uw)=a_1$,
$h(w)=f(u)$, $h(z)=f(z)$ for $z\in(S_1\setminus \{uv\})\subseteq
(S_2\setminus \{uw, w, wv, u\})$, where $S_1=V(G)\cup E(G)$,
$S_2=V(H)\cup E(H)$. Notice that the color set of colors assigned to every vertex $z\in V(H)\setminus \{u, w\}$ is as the same as one in $G$. Since $C(u, h)=\{h(ux), \alpha, a_1\}$,
$C(w, h)=\{f(u), \alpha, a_1\}$, $h(ux)\in C(u, h)$ and $h(ux)\not\in
C(w, h)$, therefore, $C(u, h)\neq C(w, h)$. Based on $d _{G}(u)\neq d
_{G}(x)$, $d _{G}(w)\neq d _{G}(v)$, we have $C(u, h)\neq C(x, h)$,
$C(w, h)\neq C(v, h)$. We conclude that $h$ is an AVDTC of $H$, and $\chi\, ''_{as}(H) \leq \chi\, ''_{as} (G)$.
Case 2 $f(x)=\alpha$.
Case 2.1 $f(v)\neq f(ux)$.
Let $h(u)=f(v)$, $h(uw)=f(u)$, $h(w)\in
C\setminus\{\alpha, h(u), h(v)\}$. And $h(z)=f(z)$ for $z\in(S_1\setminus \{uv\})\subseteq (S_2\setminus \{uw, w, wv, u\})$, where $S_1=V(G)\cup E(G)$ and $S_2=V(H)\cup E(H)$. We can see that the color set of each vertex $z\in V(H)\setminus \{u, w\}$ is as the same as one in $G$. Notice that $C(u, h)=\{h(ux), h(u), h(uw)\}$,
$C(w, h)=\{\alpha, h(uw), h(w)\}$; for $\alpha\in C(w, h)$,
$\alpha\not\in C(u, h)$, Thereby, $C(u, h)\neq C(w, h)$. Since $d_{G}(w)\neq d_{G}(v)$ for $d_{G}(u)\neq d _{G}(x)$, we obtain $C(u, h)\neq C(x, h)$ and $C(w, h) \neq C(v, h)$. The above facts show that $h$ is an AVDTC of $H$, and $\chi\, ''_{as}(H)\leq
\chi\, ''_{as} (G)$.
Case 2.2 $f(v)=f(ux)$.
In this case, we cannot give graph $H$ an AVDTC with four colors. Then we prove that graph $H$ satisfies an AVDTC with five colors. Let $h(u)=f(vw_1)$, $h(uw)=f(vw_2)$, $h(w)\in
[1, 5]\setminus\{\alpha, f(v), f(vw_1), f(vw_2)\}$. And $h(z)=f(z)$ for $z\in(S_1\setminus \{uv\})\subseteq (S_2\setminus
\{uw, w, wv, u\})$, where $S_1=V(G)\cup E(G)$ and $S_2=V(H)\cup
E(H)$. We can see that the color set of each vertex $z\in
V(H)\setminus \{u, w\}$ is as the same as one in $G$. Notice that $C(u, h)=\{f(v), f(vw_1), f(vw_2)\}$,
$C(w, h)=\{\alpha, f(vw_2), h(w)\}$; for $h(w)\in C(w, h)$,
$h(w)\not\in C(u, h)$, Thereby, $C(u, h)\neq C(w, h)$. Since $d_{G}(w)\neq d_{G}(v)$ for $d_{G}(u)\neq d _{G}(x)$, we obtain $C(u, h)\neq C(x, h)$ and $C(w, h) \neq C(v, h)$. The above facts show that $h$ is an $5$-AVDTC of $H$, which implies $\chi\, ''_{as}(H)\leq 5$.
The lemma is covered.
Lemma 2.3 By Lemma $2.2$, we can construct a graph $G$ with maximum degree $3$ such that $G$ has a path $P=ux_1x_2x_3v$, where $d_G(u)=d_G(v)=3$, $d_G(x_i)=2$ for $i=1, 2, 3$. Adding a new vertex $w$ to $G$, and then joining $w$ and $x_2$ by an edge produces a new graph $H$. Then $\chi\, ''_{as}(H)\leq
\chi\, ''_{as}(G)$.
Proof Let $f$ be an AVDTC of a simple graph $G$, and $C$ is the color set under the coloring $f$. We define a total coloring $\tau$ of $H$ in the following: $\tau(wx_2)\in C\setminus
C(x_2, f)$, $\tau(w)= f(x_1x_2)$ and $\tau(z)=f(z)$, $z\in V(H)\cup
E(H)\setminus\{wx_2, w\}$. Clearly, $\tau$ is an AVDTC of $H$, that is, $\chi\, ''_{as}(H)\leq \chi\, ''_{as} (G)$, as desired.
By Lemma $2.3$, we can construct a graph $G$ with maximum degree $3$ such that $G$ contains an edge $uv$ that $d_G(u)=1$,
$d_G(v)=\Delta(G)=3$.
Lemma 2.4 Let $G$ be a simple graph with maximum degree $3$. If $d_G(u)=1$, $d_G(v)=\Delta(G)=3$ for an edge $uv\in E(G)$, and then replacing edge $uv$ by a path $uw_0v$ ($w_0\not\in V(G)$) produces a new graph $H$ holding $\chi\, ''_{as}(H) \leq
\chi\, ''_{as} (G)$.
Proof Let $f$ be a $k$-AVDTC of a simple graph $G$ of maximum degree $3$ with $k\geq \chi\, ''_{as}(G)$. Let $f(uv)=\alpha$ for an edge $uv\in E(G)$. Let $N_{G}(v)=\{u, w_1, w_2\}$. We need only consider the colors assigned to the vertex $w_0$ and the edges $uw_0, w_0v$ in $H$. Define a total coloring $g$ of $G$ as following: $g(w_0v)=\alpha$,
$g(u)= \alpha$, $g(uw_0)=f(u)$, $g(w_0)\in C \setminus
\{\alpha, g(v), g(uw_0)\}$; $g(z)=f(z)$ for $z\in(S_1\setminus
\{uv\})\subseteq (S_2\setminus \{uw_0, w_0, w_0v, u\})$, where $S_1=V(G)\cup E(G)$, $S_2=V(H)\cup E(H)$. Observe that the color set of each vertex $z\in V(H)\setminus \{w\}$ keeps no change $G$. Obviously, $C(u, g)\neq C(w_0, g)$ and $C(w_0, g)\neq C(v, g)$ since $d _{H}(w_0)=2$. Hence, $g$ is an AVDTC of $G$, which it leads to $\chi\, ''_{as}(H)\leq \chi\, ''_{as} (G)$, we are done.
Lemma 2.5 Let $G$ be a simple graph with maximum degree $3$. Suppose that $G$ has no pair of vertices with the same degree and every vertices of degree $1$ is adjacent only to vertex of degree $3$. Joining a pair of vertices of degree $1$ with an edge produces a new graph $H$. Then $\chi\, ''_{as}(H)\leq
\chi\, ''_{as}(G)$.
Proof Let $f$ be an adjacent total coloring of $G$. Let $f^{*}$ be a total coloring of $H$.
Graph $H$ is constructed from $G$, see in Figure 3(a).
Case 1 $f(v_1)=f(v_2)$. Set $f^{*}(v_2)=f(vv_1)$,
$f^{*}(v_1v_2)=f(v)$, $f^{*}(x)=f(x), x\in V(G)\cup E(G)\setminus
\{v_2\}$. Then we have $C(u_1, f^{*})\neq C(v_1, f^{*})$ for $f^{*}(v_1)\not\in C(v_2, f^{*})$, $f^{*}(v_1)\in C(v_1, f^{*})$.
$C(v, f^{*})\neq C(v_1, f^{*})$, $C(v, f^{*})\neq C(v_2, f^{*})$ for $|C(v, f^{*})|=4$, $|C(v_1, f^{*})|=|C(v_2, f^{*})|=3$. Therefore,
$f^{*}$ is an adjacent total coloring of $H$, and $\chi\, ''_{as}(H)\leq \chi\, ''_{as}(G)$.
Case 2 $f(v_1)\neq f(v_2)$. Set $f^{*}(v_1v_2)=f(v)$,
$f^{*}(x)=f(x), x\in V(G)\cup E(G)$. Then we have $C(u_1, f^{*})\neq
C(v_1, f^{*})$ for $f^{*}(vv_2)\not\in C(v_1, f^{*})$,
$f^{*}(vv_2)\in C(v_2, f^{*})$. $C(v, f^{*})\neq C(v_1, f^{*})$,
$C(v, f^{*})\neq C(v_2, f^{*})$ for $|C(v, f^{*})|=4$,
$|C(v_1, f^{*})|=|C(v_2, f^{*})|=3$. Therefore, $f^{*}$ is an adjacent total coloring of $H$, and $\chi\, ''_{as}(H)\leq
\chi\, ''_{as}(G)$.
Graph $H$ is constructed from $G$, see in Figure 3(b). Set
| $
\begin{eqnarray*}&& f^{*}(v_1)=f(u), f^{*}(vv_1)=f(u_1),
f^{*}(wv)=f(u), \\
&& f^{*}(v)=C(v, f)\setminus \{f^{*}(v_1),
f^{*}(w), f^{*}(wv), f^{*}(vv_1)\}, \\
&& f^{*}(vv_2)=C(v, f)\setminus
\{f^{*}(v), f^{*}(wv), f^{*}(vv_1)\}, \\
&& f^{*}(u_1v_1)=C(v, f)\setminus
\{f^{*}(u_1), f^{*}(v_1), f^{*}(uu_1), f^{*}(vv_1)\}, \\&&
f^{*}(v_2)=C(v, f)\setminus \{f^{*}(v), f^{*}(vv_2)\}, \\
&& f^{*}(x)=f(x), x\in V(G)\cup E(G)\setminus
\{v, v_1, v_2, vv_1, vv_2, wv\}. \end{eqnarray*}
$ |
Then we have
| $
\begin{eqnarray*}&& C(u_1, f^{*})\neq C(v_1, f^{*})~{\rm for}~ f^{*}(u)\not\in
C(u_1, f^{*}), f^{*}(u)\in C(v_1, f^{*}); \\
&& C(v, f^{*}) \neq C(v_1, f^{*}), C(v, f^{*})\neq C(v_2, f^{*})~{\rm
for}~|C(u, f^{*})|=|C(v, f^{*})|=4, \\&&
|C(v_1, f^{*})|=|C(v_2, f^{*})|=3.\end{eqnarray*}
$ |
Therefore, $f^{*}$ is an adjacent total coloring of $H$, and $\chi\, ''_{as}(H)\leq
\chi\, ''_{as}(G)$.
The lemma is completed.
Theorem 2.6 Let $H$ be a simple graph with maximum degree $3$. Then $\chi\, ''_{as}(H)\leq 5$ if $H$ has no adjacent $\Delta$-vertices.
Proof The theorem is proved in three cases as following:
Case 1 Let $H$ be a tree with $\Delta(H)=3$, by Lemma 1.4, $\chi\, ''_{as}(H)=4$ if $H$ contains no adjacent $\Delta$-vertices.
Case 2 If every vertex of degree $2$ is adjacent only to vertices of degree $3$ and minimum degree is $2$ in the graph $H$ of the theorem, we have $\chi\, ''_{as}(H)=4$ by Lemma $2.1$.
Case 3 If $H$ contains $2$-degree vertices such that they are adjacent to some $2$-degree vertices or $1$-degree vertices, or $3$-degree vertices are adjacent to some $1$-degree vertices. In this case, we can use the methods in the proofs of Lemmas $2.2$, $2.3$, $2.4$ and $2.5$ to construct $H$ from a simple graph $G$ such that
(1) $G$ is a simple graph with $\Delta(G)=3$, $\delta(G)=2$ and every vertex of degree $2$ is adjacent only to two vertices of degree $3$;
(2) $G$ is a simple graph with $\Delta(G)=3$ and no pair of vertices with the same degree, except some cycles with order $3$ or $5$ have adjacent vertices of degree $2$. Lemmas $2.2$,
$2.3$, $2.4$ and $2.5$ enable us to obtain $\chi\, ''_{as}(H)\leq
5$.
The Theorem is completed.
2014, Vol. 34 
PDF