A New Proof for a Result on the Inclusion Chromatic Index of Subcubic Graphs

Abstract

Let G be a graph with a minimum degree $\delta$ of at least two. The inclusion chromatic index of G, denoted by ${\chi }_{\subset }^{\prime }\left(G\right)$, is the minimum number of colors needed to properly color the edges of G so that the set of colors incident with any vertex is not contained in the set of colors incident to any of its neighbors. We prove that every connected subcubic graph G with $\delta \left(G\right)\ge 2$ either has an inclusion chromatic index of at most six, or G is isomorphic to ${\widehat{K}}_{2,3}$, where its inclusion chromatic index is seven.

1. Introduction

Graph coloring is an abstraction for partitioning a set of binary-related objects into subsets of independent objects; it has many practical applications [1]. The chromatic index and chromatic polynomials are two important parameters in graph theory. There are also many chemical applications to the chromatic index and chromatic polynomials; see ([2,3,4,5,6,7,8]). In this paper, we will study an edge coloring: inclusion-free edge coloring. Graphs in this article are assumed to be simple and undirected. Let G be a graph with minimum degree $\delta \ge 2$ and let $\varphi$ be a proper edge coloring of G. For every $v\in V\left(G\right)$, the palette of v is defined to be

$$S_{\varphi }\left(v\right)=\left\{\varphi \left(e\right)\right|eisincidenytov\}.$$

The inclusion-free edge coloring, recently introduced by Przybyłlo and Kwaśny [9], is a proper edge coloring $\varphi$ of G such that for every $uv\in E\left(G\right)$, neither $S_{\varphi }\left(u\right)\subseteq S_{\varphi }\left(v\right)$ nor $S_{\varphi }\left(v\right)\subseteq S_{\varphi }\left(u\right)$. The requirement of $\delta \ge 2$ is necessary since the palette of a degree-1 vertex is always a subset of the palette of its unique neighbor. The minimum number of colors required in an inclusion-free edge coloring of G is called the inclusion chromatic index and is denoted by ${\chi }_{\subset }^{\prime }\left(G\right)$.

Actually, the concept of the inclusion-free edge coloring was first introduced by Zhang [10], where it was named as Smarandachely adjacent vertex edge coloring. Then, Gu et al. [11] also investigated the topic and named the coloring as strict neighbor-distinguishing edge coloring. Although their names are different, they were all introduced to strengthen the adjacent-vertex-distinguishing edge coloring, or for short, AVD-edge coloring. An AVD-edge coloring of G is a proper edge coloring $\varphi$ such that for every $uv\in E\left(G\right)$, $S_{\varphi }\left(u\right)\ne S_{\varphi }\left(v\right)$; the minimum number of colors needed in an AVD-edge coloring is called the AVD chromatic index, denoted by ${\chi }_a^{\prime }\left(G\right)$. Clearly a graph G has an AVD-edge coloring if and only if G contains no isolated edges. Note that for a regular graph G, the palettes of any two vertices are different if and only if neither is contained in the other; hence, ${\chi }_a^{\prime }\left(G\right)={\chi }_{\subset }^{\prime }\left(G\right)$.

The AVD-edge coloring has attracted the attention of several groups of graph theorists. It was conjectured by Zhang et al. [12] that ${\chi }_a^{\prime }\left(G\right)\le \Delta +2$ for any connected graph G with $\left|V\right(G\left)\right|\ge 3$ that is not the cycle $C_5$. Balister et al. [13] proved that the conjecture holds for the class of bipartite graphs and for the class of subcubic graphs; they also showed that in general, ${\chi }_a^{\prime }\left(G\right)\le \Delta +O(log\chi \left(G\right))$ where $\chi \left(G\right)$ is the chromatic number of G. More recently, Hatami [14] showed that ${\chi }_a^{\prime }\left(G\right)\le \Delta +300$.

Despite the similarity between the two invariant ${\chi }_a^{\prime }\left(G\right)$ and ${\chi }_{\subset }^{\prime }\left(G\right)$, the upper bound for ${\chi }_{\subset }^{\prime }\left(G\right)$ seems to be much larger than that of ${\chi }_a^{\prime }\left(G\right)$. Przybyłlo and Kwaśny [9] showed that if G is a complete bipartite graph, then ${\chi }_{\subset }^{\prime }\left(G\right)=(1+\frac{1}{\delta -1})\Delta$, where $\delta$ is the minimum degree of G. By using a greedy coloring scheme, they showed that in general ${\chi }_{\subset }^{\prime }\left(G\right)\le 3\Delta -1$ where $\Delta$ is the maximum degree of G. They made the following conjecture:

Conjecture 1.

Let G be a connected graph with minimum degree$\delta \ge 2$and maximum degree$\Delta$that is not isomorphic to$C_5$. Then

$${\chi }_{\subset }^{\prime }\left(G\right)\le \lceil (1+\frac{1}{\delta -1})\Delta \rceil .$$

Using a probabilistic approach, Przybyłlo and Kwaśny [9] proved the following upper bound for ${\chi }_{\subset }^{\prime }\left(G\right)$, which is not as strong as the conjectured bound in Conjecture 1.

Theorem 1.

If G is a graph with minimum degree $\delta \ge 2$ and maximum degree Δ, then

$${\chi }_{\subset }^{\prime }\left(G\right)\le (1+\frac{4}{\delta })\Delta +O({\Delta }^{\frac{2}{3}}{log}^4\Delta ).$$

It turns out that there exists a class of exceptional graphs to Conjecture 1 in the case of $\delta =2$: for $\Delta \ge 3$, let ${\widehat{K}}_{2,\Delta }$ be the graph obtained from the complete bipartite graph $K_{2,\Delta }$ by subdividing an edge exactly once; see Figure 1. It is easy to check that no two edges of ${\widehat{K}}_{2,\Delta }$ can receive the same color in an inclusion-free edge coloring; hence, ${\chi }_{\subset }^{\prime }\left({\widehat{K}}_{2,\Delta }\right)=2\Delta +1$, which is the number of edges of ${\widehat{K}}_{2,\Delta }$.

We strongly believe that ${\widehat{K}}_{2,\Delta }$ may be the only exception to Conjecture 1. So Conjecture 1 needs to be slightly modified by adding the condition that G is not isomorphic to ${\widehat{K}}_{2,\Delta }$. Gu et al. [11] confirmed the modified conjecture for the class of subcubic graphs. A graph G is $formal$ if $\delta \left(G\right)\ge 2$. They proved the following result:

Theorem 2.

Let G be a connected formal subcubic graph. Then ${\chi }_{\subset }^{{}^{\prime }}\left(G\right)\le 7$, and moreover, ${\chi }_{\subset }^{{}^{\prime }}\left(G\right)=7$ if and only if G is isomorphic to the graph ${\widehat{K}}_{2,3}$.

They proved the result by contradiction. Let G be a counterexample with a minimal number of edges, by establishing a series of auxiliary claims, they showed that G does not contain a 2-vertex adjacent to two 2-vertices, and any 3-vertex of G cannot be adjacent to a 2-vertex, that is, G must be 3-regular, and hence, ${\chi }_{\subset }^{{}^{\prime }}\left(G\right)\le 5$, a contradiction.

In this paper, we will give a shorter proof of this theorem. We also prove the result by contradiction. First, we establish a lemma for forbidden colors and use it to exclude some structures. We also show that G does not contain a 2-vertex adjacent to two 2-vertices, i.e., G contains no k-thread with $k\ge 3$, and G does not contain a 3-cycle with one 2-vertex, and a 4-cycle with two non-adjacent 2-vertices. Then, we show that if G contains a 1-thread or 2-thread, it must be isomorphic to ${\widehat{K}}_{2,3}$.

2. Proof of the Main Result

Let G be a connected subcubic graph with $\delta \left(G\right)=2$. Suppose that ${\chi }_{\subset }^{\prime }\left(G\right)\ge 7$. We pick a graph G such that $\left|V\right(G\left)\right|+\left|E\right(G\left)\right|$ is as small as possible. By a $good$ $coloring$, we mean an inclusion-free edge coloring using at most six colors. If G and H are two graphs with $\left|E\right(H\left)\right|+\left|V\right(H\left)\right|<\left|E\right(G\left)\right|+\left|V\right(G\left)\right|$, we will say that H is smaller than G. We will show that G is isomorphic to ${\widehat{K}}_{2,3}$.

Let $C=\{1,2,3,4,5,6\}$ be a set of six colors. Suppose that $\varphi$ is a good coloring of a proper subgraph $G^{\prime }$ of G using colors from C. Let $e=uv$ be an edge in $E\left(G\right)\setminus E\left(G^{\prime }\right)$. We denote by $A_{\varphi }\left(e\right)$ the set of colors that are available for e. To color e, one cannot use a color from $S_{\varphi }\left(u\right)$; moreover, for each neighbor $v^{\prime }$ of u other than v, if by assigning a color $\alpha$ to e, we would have either $S_{\varphi }\left(u\right)\subseteq S_{\varphi }\left(v^{\prime }\right)$ or $S_{\varphi }\left(v^{\prime }\right)\subseteq S_{\varphi }\left(u\right)$, then the color $\alpha$ cannot be used for e. We call these two types of colors the forbidden colors of e by the vertex u, denoted by $F_{\varphi }(e,u)$. It follows that $A_{\varphi }\left(e\right)=C\setminus (F_{\varphi }(e,u)\cup F_{\varphi }(e,v))$.

For simplicity, we use k-vertex to denote a vertex with degree k. Similarly, by k-neighbor of a vertex u, we mean a neighbor of u that has degree k.

Lemma 1.

Suppose that $G^{\prime }$ is a proper subgraph of G with $\delta \left(G^{\prime }\right)=2$ and that ϕ is a good coloring of $G^{\prime }$. Let $e=uv$ be an edge in $E\left(G\right)\setminus E\left(G^{\prime }\right)$, where u is a 2-vertex of $G^{\prime }$. Then

• $|F_{\varphi }(e,u)|=2$ if both neighbors of u in $G^{\prime }$ are 3-vertices;
• $|F_{\varphi }(e,u)|=3$ if exactly one neighbor of u in $G^{\prime }$ is a 3-vertex;
• $|F_{\varphi }(e,u)|\le 4$ if both neighbors of u in $G^{\prime }$ are 2-vertices.

Proof. 

Let $v^{\prime }$ and $v^{″}$ be the two neighbors of u in $G^{\prime }$. Since $\varphi$ is a good coloring of $G^{\prime }$, $\varphi \left(u{v}^{″}\right)\notin S_{\varphi }\left(v^{\prime }\right)$. Therefore, no matter what color we assign to the edge $uv$, we will have that $S_{\varphi }\left(u\right)⊈S_{\varphi }\left(v^{\prime }\right)$. Now if $v^{\prime }$ is a 3-vertex of $G^{\prime }$, then the only color in $S_{\varphi }\left(v^{\prime }\right)$ that is forbidden for e is $\varphi \left(u{v}^{\prime }\right)$; while if $v^{\prime }$ is a 2-vertex of $G^{\prime }$, then neither color in $S_{\varphi }\left(v^{\prime }\right)$ can be used for e since we require $S_{\varphi }\left(v^{\prime }\right)⊈S_{\varphi }\left(u\right)$. By symmetry, the same holds for $v^{″}$. So Lemma 1 follows immediately. (Note that we may have that $|F_{\varphi }(e,u)|=3$ in the case of $d_{G^{\prime }}\left(v^{\prime }\right)=d_{G^{\prime }}\left(v^{″}\right)=2$: this happens when $S_{\varphi }\left(v^{\prime }\right)\cap S_{\varphi }\left(v^{″}\right)\ne \varnothing$.) □

Actually, Lemma 1 can be extended to more general situations: let G be a connected graph with $\delta \left(G\right)\ge 2$. Suppose that $G^{\prime }$ is a proper subgraph of G with $\delta \left(G^{\prime }\right)\ge 2$ and that $\varphi$ is an inclusion-free edge coloring of $G^{\prime }$. Let $e=uv$ be an edge in $E\left(G\right)\setminus E\left(G^{\prime }\right)$. Then $|F_{\varphi }(e,u)|\le d_u+N_u$, where $d_u$ is the degree of u in $G^{\prime }$, and $N_u$ is the number of neighbors of u in $G^{\prime }$ with degree no more than $d_u$.

For integer $k\ge 0$, a k-thread of G is a path $P=v_0{v}_1{v}_2\cdots v_{k+1}$ of length $k+1$ such that both $v_0$ and $v_{k+1}$ are 3-vertices, and each of $v_1$, $v_2$, ⋯, $v_k$ is a 2-vertex. So a 0-thread is an edge that is incident to two 3-vertices. A k-thread P is called separating if deleting all the internal vertices in P yields a disconnected subgraph of G.

Lemma 2.

G contains no separating k-thread for $k\ge 0$.

Proof. 

Let $P=v_0{v}_1{v}_2\cdots v_{k+1}$ be a separating k-thread and let $G^{\prime }$ be the subgraph of G obtained by deleting all the internal vertices in P. Since $G^{\prime }$ is disconnected, we assume that $G_1$ and $G_2$ are the two components of $G^{\prime }$ with $v_0\in V\left(G_1\right)$ and $v_{k+1}\in V\left(G_2\right)$. Since $G^{\prime }$ is a proper subgraph of G, $G^{\prime }$ has a good coloring $\varphi$. We will extend $\varphi$ to G by assigning colors to the edges on the thread P.

First we assume that $k\ge 1$. By permuting colors in $G_1$ if necessary, we may assume that $S_{\varphi }\left(v_0\right)=S_{\varphi }\left(v_{k+1}\right)$. Clearly $v_0$ is a 2-vertex in $G^{\prime }$. By Lemma 1, $|F_{\varphi }(v_0{v}_1,v_0)|\le 4$, and hence, $|A_{\varphi }\left(v_0{v}_1\right)|\ge 2$. By symmetry, $|A_{\varphi }\left(v_k{v}_{k+1}\right)|\ge 2$. So we may assign distinct colors to $v_0{v}_1$ and $v_k{v}_{k+1}$, then color all other edges on the thread one by one in the following order: $v_1{v}_2$, $v_2{v}_3$, ⋯, $v_{k-1}{v}_k$. Note that in each step, the edge to be colored forbids at most five colors, and hence, it has at least one color available. So we obtain a good coloring of G.

Next assume that $k=0$, i.e., G has a cut edge that is incident to two 3-vertices. Then we can permute colors in $G_1$ so that $F_{\varphi }(v_0{v}_1,v_1)\subseteq F_{\varphi }(v_0{v}_1,v_0)$ if $|F_{\varphi }(v_0{v}_1,v_1)|\le |F_{\varphi }(v_0{v}_1,v_0)|$ or $F_{\varphi }(v_0{v}_1,v_0)\subseteq F_{\varphi }(v_0{v}_1,v_1)$ otherwise; hence, there are at least two colors available for $v_0{v}_1$ and it can be colored.

In each case, we obtain a good coloring of G, contrary to our assumption. Therefore, G contains no separating k-thread for $k\ge 0$. □

For general case, suppose that G is a connected graph with $\delta \left(G\right)\ge 2$, $P=v_0{v}_1{v}_2\cdots$$v_{k+1}$ is a separating k-thread in G. Let $G^{\prime }$ be the graph obtained by deleting all the internal vertices of P, and $G_1$, $G_2$ be the two components of $G^{\prime }$. By the similar proof as Lemma 2, we have ${\chi }_{\subset }^{{}^{\prime }}\left(G\right)\le max\{{\chi }_{\subset }^{{}^{\prime }}\left(G_1\right),{\chi }_{\subset }^{{}^{\prime }}\left(G_2\right),|F_{\varphi }(v_0{v}_1,v_0)|,|F_{\varphi }(v_k{v}_{k+1},v_{k+1})\left|\right\}+3$. Since $|F_{\varphi }(e,u)|\le d_u+N_u\le 2d_u$, ${\chi }_{\subset }^{{}^{\prime }}\left(G\right)\le max\{{\chi }_{\subset }^{{}^{\prime }}\left(G_1\right),{\chi }_{\subset }^{{}^{\prime }}\left(G_2\right),2d_{v_0},2d_{v_{k+1}}|\}+3$.

Lemma 3.

Let $G^{\prime }$ be a subgraph of G with $\delta \left(G^{\prime }\right)\ge 2$. Suppose that $P=v_0{v}_1{v}_2\cdots v_{k+1}$ is a k-thread in $G^{\prime }$ with $k\ge 3$, then $G^{\prime }$ has a good coloring ϕ such that $\varphi \left(v_0{v}_1\right)=\varphi \left(v_k{v}_{k+1}\right)$. In particular, G contains no k-thread with $k\ge 3$.

Proof. 

First assume that $v_0$ is not adjacent to $v_{k+1}$. Then let $G^{″}$ be the graph obtained by adding the edge $v_0{v}_{k+1}$ to $G^{\prime }\setminus \{v_1,v_2,\cdots v_k\}$. Clearly $\delta \left(G^{″}\right)\ge 2$. So $G^{″}$ has a good coloring ${\varphi }^{\prime }$. We can construct a good coloring $\varphi$ of $G^{\prime }$ as follows: $\varphi \left(v_0{v}_1\right)=\varphi \left(v_k{v}_{k+1}\right)={\varphi }^{\prime }\left(v_0{v}_{k+1}\right)$; $\varphi \left(e\right)={\varphi }^{\prime }\left(e\right)$ for all $e\in E\left(G^{\prime }\right)\cap E\left(G^{″}\right)$. We color the remaining edges in the following order: $v_1{v}_2$, $v_2{v}_3$, ⋯, $v_{k-1}{v}_k$. Since $k\ge 3$, at each step, the edge to be colored forbids at most five colors. Therefore, all edges of P can be colored and we obtain a good coloring $\varphi$ of $G^{\prime }$ with $\varphi \left(v_0{v}_1\right)=\varphi \left(v_k{v}_{k+1}\right)$.

Next assume that $v_0$ is adjacent to $v_{k+1}$. Let $G^{″}=G^{\prime }\setminus \{v_1,v_2,\cdots v_k\}$ and let $\varphi$ be a good coloring of $G^{″}$. Then each of $A_{\varphi }\left(v_0{v}_1\right)$ and $A_{\varphi }\left(v_k{v}_{k+1}\right)$ has size at least three. Since $\varphi \left(v_0{v}_{k+1}\right)\notin A_{\varphi }\left(v_0{v}_1\right)\cup A_{\varphi }\left(v_k{v}_{k+1}\right)$. We have that $A_{\varphi }\left(v_0{v}_1\right)\cap A_{\varphi }\left(v_k{v}_{k+1}\right)\ne \varnothing$. We may pick $\alpha \in A_{\varphi }\left(v_0{v}_1\right)\cap A_{\varphi }\left(v_k{v}_{k+1}\right)$ and assign it to $v_0{v}_1$ and $v_k{v}_{k+1}$. Similar as above, the remaining edges of P can be colored in the order: $v_1{v}_2$, $v_2{v}_3$, ⋯, $v_{k-1}{v}_k$. Therefore, $G^{\prime }$ has a good coloring $\varphi$ such that $\varphi \left(v_0{v}_1\right)=\varphi \left(v_k{v}_{k+1}\right)$.

In particular, if $G^{\prime }=G$, and G has a k-thread with $k\ge 3$, then G has good coloring $\varphi$, contrary to our assumption. Hence, G contains no k-thread with $k\ge 3$. □

Lemma 3 can also be extended to more general situations: let G be a connected graph with $\delta \left(G\right)\ge 2$, and H be a graph obtained from G by subdividing an edge with at least 3 vertices, then ${\chi }_{\subset }^{{}^{\prime }}\left(H\right)\le max\{{\chi }_{\subset }^{{}^{\prime }}\left(G\right),6\}.$

Lemma 4.

Let P be a 1- or 2-thread in G. Then the two 3-vertices on P are not adjacent to each other.

Proof. 

Suppose that $P=uwv$ is a 1-thread in G where u is adjacent to v. Let $u^{\prime }$ (resp. $v^{\prime }$) be the neighbor of u (resp. v) not on P. Note that $G^{\prime }=G\setminus w$ is a subcubic graph with minimum degree 2. By our assumption on G, $G^{\prime }$ has good coloring $\varphi$. Since $d_{G^{\prime }}\left(u\right)=d_{G^{\prime }}\left(v\right)=2$, $\varphi \left(uv\right)\notin S_{\varphi }\left(u^{\prime }\right)$ and $\varphi \left(uv\right)\notin S_{\varphi }\left(v^{\prime }\right)$. It is easy to see that if $u^{\prime }$ is a 3-vertex, $|A_{\varphi }\left(uw\right)|\ge 3$ and if $u^{\prime }$ is a 2-vertex, $|A_{\varphi }\left(uw\right)\ge 2$. By symmetry, $|A_{\varphi }\left(vw\right)|\ge 2$. So we can assign two distinct colors to $uw$ and $vw$ to obtain a good coloring of G, a contradiction.

The case when P is a 2-thread can be proved in a similar manner. □

Lemma 5.

Let $uvxyu$ be a 4-cycle of G. If $d_G\left(u\right)=d_G\left(x\right)=3$ and $d_G\left(v\right)=d_G\left(y\right)=2$, then G is isomorphic to ${\widehat{K}}_{2,3}$.

Proof. 

Let $u^{\prime }$ ( resp. $x^{\prime }$) be the neighbor of u (resp. x) other than v and y.

First we assume that $u^{\prime }=x^{\prime }$. In this case, if $d_G\left(u^{\prime }\right)=2$, then $G\cong K_{2,3}$, contrary to our assumption that ${\chi }_{\subset }^{\prime }\left(G\right)\ge 7$. If $d_G\left(u^{\prime }\right)=3$, let w be the neighbor of $u^{\prime }$ other than $u,x$, then the edge $u^{\prime }w$ lies in a separating k-thread with $k\ge 0$, contrary to Lemma 2. Hence, $u^{\prime }\ne x^{\prime }$.

Let $\varphi$ be a good coloring of $G^{\prime }=G\setminus v$. Then $A_{\varphi }\left(uv\right)=C\setminus (F_{\varphi }(uv,u)\cup S_{\varphi }\left(x\right))$. So if one of $u^{\prime }$ and $x^{\prime }$ is a 3-vertex, then by Lemma 1, one of $uv$ and $vx$ has at least two colors available and the other one has at least one color available. So they can both be colored. Therefore, $d_G\left(x^{\prime }\right)=d_G\left(u^{\prime }\right)=2$.

Note that if $u^{\prime }$ is adjacent to $x^{\prime }$, then $G\cong {\widehat{K}}_{2,3}$. So we may assume that $u^{\prime }$ is not adjacent to $x^{\prime }$. Let $G^{\prime }$ be the graph obtained by adding the edge $u^{\prime }{x}^{\prime }$ in $G\setminus \{u,v,x,y\}$. Clearly $\delta \left(G^{\prime }\right)\ge 2$. So $G^{\prime }$ has a good coloring ${\varphi }^{\prime }$. Since $d_{G^{\prime }}\left(u^{\prime }\right)=d_{G^{\prime }}\left(x^{\prime }\right)=2$, the edges $u^{\prime }{u}^{″},u^{\prime }{x}^{\prime },x^{\prime }{x}^{″}$ receive different colors, where $u^{″}$ (resp. $x^{″}$) be the neighbor of $u^{\prime }$ (resp. $x^{\prime }$). We may assume that $\varphi \left(u^{\prime }{u}^{″}\right)=1,\varphi \left(u^{\prime }{x}^{\prime }\right)=2,\varphi \left(x^{\prime }{x}^{″}\right)=3$, then we color the edges $u{u}^{\prime },uv,uy,vx,xy,x{x}^{\prime }$ as follows: $\varphi \left(u{u}^{\prime }\right)=\varphi \left(x{x}^{\prime }\right)=2$, $\varphi \left(uv\right)=3$, $\varphi \left(vx\right)=4$, $\varphi \left(xy\right)=5$, $\varphi \left(uy\right)=6$. It is easy to see that this coloring is a good coloring of G, contrary to our assumption. □

Recall that Balister et al. [13] showed that a 3-regular graph has an AVD chromatic index of at most 5. Since the inclusion chromatic index is the same as the AVD chromatic index for regular graphs, every 3-regular graph has an inclusion chromatic index of at most 5. Since ${\chi }_{\subset }^{\prime }\left(G\right)\ge 7$ by our assumption, G must have at least one 2-vertex. By Lemma 3, G contains either a 1-thread or a 2-thread. Let P be a k-thread with $k=1$ or 2, and let $G^{\prime }$ be the graph obtained from G by deleting all internal vertices of P. By Lemma 2, $G^{\prime }$ is connected. Clearly, $G^{\prime }$ is a subcubic graph with minimum degree 2 and is smaller than G. By our assumption on G, $G^{\prime }$ has a good coloring $\varphi$. We will extend $\varphi$ to a good coloring of G by assigning appropriate colors for all edges on the thread P.

Lemma 6.

If P is a 2-thread in G, then G is isomorphic to ${\widehat{K}}_{2,3}$.

Proof. 

Suppose that $P=u{u}^{\prime }{v}^{\prime }v$ is a 2-thread where $d_G\left(u^{\prime }\right)=d_G\left(v^{\prime }\right)=2$ and $d_G\left(u\right)=d_G\left(v\right)=3$. By Lemma 2, $u\ne v$, and by Lemma 4, u is not adjacent to v. Let $u_1$ and $u_2$ be the neighbors of u other than $u^{\prime }$ and let $v_1$ and $v_2$ be the neighbors of v other than $v^{\prime }$.

Note that the edge $u{u}^{\prime }$ can be colored by any color not in $F_{\varphi }(u{u}^{\prime },u)$. By Lemma 1, $|A_{\varphi }\left(u{u}^{\prime }\right)|\ge 2$; by symmetry, $|A_{\varphi }\left(v{v}^{\prime }\right)|\ge 2$. The edge $u^{\prime }{v}^{\prime }$ can be colored by any color not in $S_{\varphi }\left(u\right)\cup S_{\varphi }\left(v\right)$, so $|A_{\varphi }\left(u^{\prime }{v}^{\prime }\right)|\ge 2$.

Assume that there exists a 3-vertex in $\{u_1,u_2,v_1,v_2\}$, say $u_1$. Then by Lemma 1, the edge $u{u}^{\prime }$ forbids at most three colors, and hence, the edges on P can be colored in the order of $v{v}^{\prime }$, $u^{\prime }{v}^{\prime }$, and $u{u}^{\prime }$. We obtain a good coloring of G, a contradiction.

Therefore, we have that $d_G\left(u_1\right)=d_G\left(u_2\right)=d_G\left(v_1\right)=d_G\left(v_2\right)=2$. Note that if $\{u_1,u_2\}=\{v_1,v_2\}$, then G is isomorphic to ${\widehat{K}}_{2,3}$. So we may assume that $|\{u_1,u_2\}\cap \{v_1,v_2\}|\le 1$.

Case 1: $|\{u_1,u_2\}\cap \{v_1,v_2\}|=1$.

By symmetry, assume that $u_1=v_1$. Then, $u{u}^{\prime }{v}^{\prime }v{u}_{1}u$ form a 5-cycle, call it $C_1$. Let $G^{″}$ be the graph obtained from $G\setminus \{u^{\prime },v^{\prime },u_1\}$ by identifying u and v. Let w be the new identified vertex, and let $u_2^{\prime }$ (resp $v_2^{\prime }$) be the neighbor of $u_2$ in $G^{″}$ other than w. Clearly, $G^{″}$ is a subcubic graph with minimum degree 2 and is smaller than G. So $G^{″}$ has a good coloring ${\psi }^{\prime }$. We extend ${\psi }^{\prime }$ to a good coloring $\psi$ of G as follows: let $\psi \left(u{u}_2\right)={\psi }^{\prime }\left(w{u}_2\right)$, $\psi \left(v{v}_2\right)={\psi }^{\prime }\left(w{v}_2\right)$, and $\psi \left(e\right)={\psi }^{\prime }\left(e\right)$ for $e\in E\left(G\right)\cap E\left(G^{″}\right)$. Now we need to assign colors to edges on $C_1$: Since ${\psi }^{\prime }$ is a good coloring of $G^{″}$, among the four edges $u{u}_2$, $u_2{u}_2^{\prime }$, $v{v}_2$ and $v_2{v}_2^{\prime }$, only $u_2{u}_2^{\prime }$ and $v_2{v}_2^{\prime }$ may share a same color. So we may assume that $\psi \left(u{u}_2\right)=1$, $\psi \left(v{v}_2\right)=2$, $\psi \left(u_2{u}_2^{\prime }\right)=3$, and $\psi \left(v_2{v}_2^{\prime }\right)=3$ or 4. In both cases, we will set $\psi \left(u{u}^{\prime }\right)=2$, $\psi \left(v{v}^{\prime }\right)=1$, $\psi \left(u{u}_1\right)=4$, $\psi \left(v{v}_1\right)=5$, and $\psi \left(u^{\prime }{v}^{\prime }\right)=6$. It is easy to check that $\psi$ is a good coloring of G, a contradiction.

Case 2: $N\left(u\right)\cap N\left(v\right)=\varnothing .$

For $x\in \{u,v\}$ and $i\in \{1,2\}$, let $x_i^{\prime }$ be the neighbor of $x_i$ other than x. By Lemmas 5 and 2, $u_1^{\prime }\ne u_2^{\prime }$ and $v_1^{\prime }\ne v_2^{\prime }$. If $u^{\prime }$ is adjacent to $u_2^{\prime }$, then by Lemma 2, one of them must have degree 3, say $d_G\left(u_1^{\prime }\right)=3$. We claim that $d_G\left(u_2^{\prime }\right)=3$, as, otherwise, this can be reduced to Case 1 by choosing the 2-thread $u{u}_2{u}_2^{\prime }{u}_1^{\prime }$ to begin with. By Lemma 3, we may choose $\varphi$ such that $\varphi \left(u_1{u}_1^{\prime }\right)=\varphi \left(u_2{u}_2^{\prime }\right)$. Note that the edge $u{u}^{\prime }$ can be assigned any color not in $S_{\varphi }\left(u_1\right)\cup S_{\varphi }\left(u_2\right)$; so $|A_{\varphi }\left(u{u}^{\prime }\right)|\ge 3$. Similarly, $|A_{\varphi }\left(u^{\prime }{v}^{\prime }\right)|\ge 2$ and $|A_{\varphi }\left(v{v}^{\prime }\right)|\ge 2$. So the edges $v{v}^{\prime }$, $u^{\prime }{v}^{\prime }$, and $u{u}^{\prime }$ can be colored in that order. □

Lemma 7.

Let $uwv{u}_{1}u$ be a 4-cycle of G with $d\left(u\right)=d\left(v\right)=d\left(u_1\right)=3$ and $d\left(w\right)=2$, and let $u_2$ (resp. $v_2$) be the neighbor of u (resp. v) other than w and $u_1$. If $d\left(u_2\right)=d\left(v_2\right)=2$, then the graph $G^{\prime }=G\setminus w$ has a good coloring ϕ so that $\varphi \left(u{u}_2\right)=\varphi \left(v{v}_2\right)$.

Proof. 

Let $u_1^{\prime }$ be the neighbor of $u_1$ other than u and v and let $u_2^{\prime }$ (resp. $v_2^{\prime }$) be the neighbor of $u_2$ (resp. $v_2$) other than u (resp. v). By Lemma 2, $u_2{v}_2\notin E\left(G\right)$. Since $G^{\prime }$ is a subcubic graph with minimum degree 2 and is smaller than G, $G^{\prime }$ has a good coloring $\varphi$. Now we remove the colors on the edges $u_2{u}_2^{\prime }$, $u{u}_2$, $u{u}_1$, $v{u}_1$, $v{v}_2$, and $v_2{v}_2^{\prime }$. Then $|A_{\varphi }\left(u{u}_2\right)|\ge 3,$ and $|A_{\varphi }\left(v{v}_2\right)|\ge 3$. Note that $|A_{\varphi }\left(u{u}_2\right)\cup A_{\varphi }\left(v{v}_2\right)|\le 5$ since $\varphi \left(u_1{u}_1^{\prime }\right)\notin A_{\varphi }\left(u{u}_2\right)\cup A_{\varphi }\left(v{v}_2\right)$. So $A_{\varphi }\left(u{u}_2\right)\cap A_{\varphi }\left(v{v}_2\right)\ne \varnothing$. Choose a color $\alpha \in A_{\varphi }\left(u{u}_2\right)\cap A_{\varphi }\left(v{v}_2\right)$ and assign it to edges $u{u}_2$ and $v{v}_2$.

If either $u_2^{\prime }=v_2^{\prime }$ or $u_2^{\prime }$ is adjacent to $v_2^{\prime }$, then each of $u_2{u}_2^{\prime }$ and $v_2{v}_2^{\prime }$ has at least two colors available. So we will color them using different colors. Now each of $u{u}_1$ and $v{u}_1$ has at least two colors available, so they can be colored as well. So we may assume that neither $u_2^{\prime }=v_2^{\prime }$ nor $u_2^{\prime }$ is adjacent to $v_2^{\prime }$, and hence, $u_2{u}_2^{\prime }$ and $v_2{v}_2^{\prime }$ may receive the same color.

Now we have that $|A_{\varphi }\left(u_2{u}_2^{\prime }\right)|\ge 1$, $|A_{\varphi }\left(u{u}_1\right)|\ge 3$, and $|A_{\varphi }\left(v{u}_1\right)|\ge 3$ and $|A_{\varphi }\left(v_2{v}_2^{\prime }\right)|\ge 1$. We then color $u_2{u}_2^{\prime }$ and $v_2{v}_2^{\prime }$ independently. The edge $u{u}_1$ (resp. $v{v}_1$) may only lose the color assigned to $u_2{u}_2^{\prime }$ (resp. $v_2{v}_2^{\prime }$). So both $u{u}_1$ and $v{v}_1$ still have at least two colors available, and hence, they can be colored. □

Finally we consider the case that P is a 1-thread.

Lemma 8.

If P is a 1-thread in G, then G is isomorphic to ${\widehat{K}}_{2,3}$.

Proof. 

Let $P=uwv$. Then by Lemma 4, u is not adjacent to v. Let $u_1,u_2$ be the neighbors of u other than w, and let $v_1,v_2$ be the neighbors of v other than w. We consider the following three cases.

Case 1: $\{u_1,u_2\}=\{v_1,v_2\}$.

Assume that $u_1=v_1$ and $u_2=v_2$. By Lemma 5, neither $u_1$ nor $u_2$ is a 2-vertex. So $d_G\left(u_1\right)=d_G\left(u_2\right)=3$. By Lemma 1, each of $uw$ and $vw$ forbids at most four colors. So they both can be colored.

Case 2: $|\{u_1,u_2\}\cap \{v_1,v_2\}|=1$

Suppose that $u_1=v_1$ and $u_2\ne v_2$. By Lemma 5, $d_G\left(u_1\right)=3$. Note that the edge $uw$ can be assigned any color not in $F_{\varphi }(uw,u)\cup S_{\varphi }\left(v\right)$ and the edge $vw$ can be assigned any color not in $F_{\varphi }(vw,v)\cup S_{\varphi }\left(u\right)$. So if one of $u_2$ and $v_2$ is a 3-vertex, then by Lemma 1, one of $uw$ and $vw$ has at least two colors available, while the other one has at least one color available. So we can extend $\varphi$ to a good coloring of G, a contradiction.

Therefore, we may assume that $d_G\left(u_2\right)=d_G\left(v_2\right)=2$. Let $u_1^{\prime }$ be the neighbor or $u_1$ other than u and v and let $u_2^{\prime }$ (resp. $v_2^{\prime }$) be the neighbors of $u_2$ (resp. $v_2$) other than u (resp. v). By Lemma 7, the graph $G^{\prime }=G\setminus w$ has a good coloring $\varphi$ so that $\varphi \left(u{u}_2\right)=\varphi \left(v{v}_2\right)$. It is easy to see that $|A_{\varphi }\left(uw\right)|\ge 2$, and $|A_{\varphi }\left(vw\right)|\ge 2$. Therefore, we may extend $\varphi$ to a good coloring of G, a contradiction.

Case 3: $\{u_1,u_2\}\cap \{v_1,v_2\}=\varnothing$

Note that $A_{\varphi }\left(uw\right)=C\setminus (F_{\varphi }(uw,u)\cup S_{\varphi }\left(v\right)$ and $A_{\varphi }\left(vw\right)=C\setminus (F_{\varphi }(vw,v)\cup S_{\varphi }\left(u\right)$. Therefore, if at least three of $u_1$, $u_2$, $v_1$, and $v_2$ are 3-vertices, then by Lemma 1, one of the edges $uw$ and $vw$ has at least two colors available, while the other one has at least one color available. So we can extend $\varphi$ to a good coloring of G.

Therefore, at most, two of the vertices in $\{u_1,u_2,v_1,v_2\}$ are 3-vertices. For $i\in \{1,2\}$ we will use $u_i^{\prime }$ (resp. $v_i^{\prime }$) to denote a neighbor of $u_i$ (resp. $v_i$) different from u (resp. v). By symmetry, it suffices to consider the following two subcases:

Subcase 3.1: both $u_1$ and $u_2$ are 2-vertices.

Since G contains no 2-thread, each of $u_1^{\prime }$ and $u_2^{\prime }$ is a 3-vertex. By Lemmas 2 and 5, $u_1^{\prime }\ne u_2^{\prime }$. So by Lemma 3, we can choose a good coloring $\varphi$ of $G\setminus w$ with $\varphi \left(u_1{u}_1^{\prime }\right)=\varphi \left(u_2{u}_2^{\prime }\right)$. Then the edge $uw$ has at least one color available. If the edge $vw$ has at least two colors available, then $\varphi$ can be extended to a good coloring of G. Therefore, at least one of $v_1$ and $v_2$ is a 2-vertex, say $v_1$. Moreover, if $S_{\varphi }\left(u\right)\cap S_{\varphi }\left(v\right)\ne \varnothing$, then one of $uw$ and $vw$ has two available colors, while the other one has at least one available color, so $\varphi$ can be extended to a good coloring of G.

So we may assume that $\varphi \left(u{u}_1\right)=1$, $\varphi \left(u{u}_2\right)=2$, $\varphi \left(v{v}_1\right)=3$, $\varphi \left(v{v}_2\right)=4$, and $\varphi \left(u_1{u}_1^{\prime }\right)=\varphi \left(u_2{u}_2^{\prime }\right)=5$. If the color $5\notin S_{\varphi }\left(v_1\right)\cup S_{\varphi }\left(v_2\right)$, or $d_G\left(v_2\right)=3$ and $5\notin S_{\varphi }\left(v_1\right)$, then we may assign color 5 to $vw$ and assign color 6 to $uw$ to obtain a good coloring of G. So we can assume that $\varphi \left(v_1{v}_1^{\prime }\right)=5$.

Observe that if $\{3,4\}⊈S_{\varphi }\left(u_1^{\prime }\right)$, say $3\notin S_{\varphi }\left(u_1^{\prime }\right)$, then by changing the color of $u{u}_1$ from 1 to 3, we obtain that $|A_{\varphi }\left(uw\right)|\ge 2$ and $|A_{\varphi }\left(vw\right)|\ge 1$. So we can extend $\varphi$ to a good coloring of G. So we have that $S_{\varphi }\left(u_1^{\prime }\right)=\{3,4,5\}$. Similarly $S_{\varphi }\left(u_2^{\prime }\right)=\{3,4,5\}$.

Next we will show that $v_2$ must be a 2-vertex. Assume that $d_G\left(v_2\right)=3$. Note that the color $3\notin S_{\varphi }\left(v_2\right)$ since $\varphi$ is a good coloring of $G^{\prime }$. So if $\{1,2\}⊈S_{\varphi }\left(v_1^{\prime }\right)$, say $1\notin S_{{\varphi }^{\prime }}\left(v_1^{\prime }\right)$, then we may change the color of $v{v}_1$ from 3 to 1, assign color 3 to $vw$ and color 6 to $uw$; we obtain a good coloring of G. So $S_{\varphi }\left(v_1^{\prime }\right)=\{1,2,5\}$. Now we can change the colors of $u{u}_1$ and $v{v}_1$ both to 6, and let $\varphi \left(uw\right)=1$ and $\varphi \left(vw\right)=3$, we obtain a good coloring of G.

Therefore, we know that $d_G\left(v_2\right)=2$. Observe that $v_2^{\prime }$ is a 3-vertex. If $S_{\varphi }\left(v_2^{\prime }\right)\ne \{1,2,6\}$, then we can pick a color $\beta \in \{1,2,6\}\setminus S_{{\varphi }^{\prime }}\left(v_2^{\prime }\right)$ and change the color of $v{v}_2$ from 4 to $\beta$; if $\beta =6$, we will also change the color of $u{u}_1$ from 1 to 6. Now we have $S_{\varphi }\left(u\right)\cap S_{\varphi }\left(v\right)\ne \varnothing$, so we can extend $\varphi$ to a good coloring of G.

Therefore, we have that $S_{\varphi }\left(v_2^{\prime }\right)=\{1,2,6\}$. We construct a good coloring ${\varphi }^{\prime }$ of $G^{\prime }=G\setminus w$ as follows: for all $e\in E\left(G^{\prime }\right)\setminus \{v{v}_1,v{v}_2,v_2{v}_2^{\prime }\}$, let ${\varphi }^{\prime }\left(e\right)=\varphi \left(e\right)$; for the edge $v_2{v}_2^{\prime }$, note that $|A_{{\varphi }^{\prime }}\left(v_2{v}_2^{\prime }\right)|\ge 2$. So we can set ${\varphi }^{\prime }\left(v_2{v}_2^{\prime }\right)\ne \varphi \left(v_2{v}_2^{\prime }\right)$. Each of $v{v}_1$ and $v{v}_2$ has at least two colors available, so they can both be colored. In the new coloring ${\varphi }^{\prime }$, since $|S_{{\varphi }^{\prime }}\left(v_2\right)\setminus S_{\varphi }\left(v_2\right)|=1$, $S_{{\varphi }^{\prime }}\left(v_2\right)\ne \{1,2,6\}$. Therefore, the coloring ${\varphi }^{\prime }$ can be extended to a good coloring of G.

Subcase 3.2: $d_G\left(u_1\right)=d_G\left(v_1\right)=3$, $d_G\left(u_2\right)=d_G\left(v_2\right)=2$.

Then $|A_{\varphi }\left(uw\right)|\ge 1$ and $|A_{\varphi }\left(vw\right)|\ge 1$. If one of $|A_{\varphi }\left(uw\right)|$ and $|A_{\varphi }\left(vw\right)|$ is at least 2, or $A_{\varphi }\left(uw\right)\ne A_{\varphi }\left(vw\right)$, then both $uw$ and $vw$ can be colored. So we may assume that $A_{\varphi }\left(uw\right)=A_{\varphi }\left(uw\right)=\left\{6\right\}$. Without loss of generality, we may further assume that $\varphi \left(u{u}_1\right)=1,\varphi \left(u{u}_2\right)=2,\varphi \left(v{v}_1\right)=3,\varphi \left(v{v}_2\right)=4,\varphi \left(u_2{u}_2^{\prime }\right)=\varphi \left(v_2{v}_2^{\prime }\right)=5$.

By a similar argument used in Subcase 3.1, we deduce that $S_{\varphi }\left(u_2^{\prime }\right)=\{3,4,5\}$ and $S_{\varphi }\left(v_2^{\prime }\right)=\{1,2,5\}$. Then we can change the colors of $u{u}_2$ and $v{v}_2$ both to 6. Now we get a good coloring of G by assigning color 2 to $uw$ and color 4 to $vw$. □

This completes our proof for Theorem 2.

3. Conclusions

In this paper, we present a slightly different proof of a result proved by Gu et al. [11]. Lemma 1 for forbidden colors is crucial for our proof, and it can be extended to a more general setting. For $\Delta \ge 4$, Conjecture 1 is still open. It will be interesting to consider the case $\Delta =4$ for our future work.