On Strong Edge-Coloring of Claw-Free Subcubic Graphs

Abstract

A strong edge-coloring of a graph G is a proper edge coloring such that every path of length 3 uses three different colors. The strong chromatic index of G, denoted by $\chi _{s}^{\prime }(G)$, is the least possible number of colors in a strong edge-coloring of G. In this paper, we prove that if G is a claw-free subcubic graph other than the prism graph, then $\chi _{s}^{\prime }(G)\le 8$.

1 Introduction

Let G be a simple connected graph with vertex set V(G) and edge set E(G). Its order is |V(G)|, and its size is |E(G)|. The maximum and the minimum degrees of G are denoted $\delta (G)$ and $\varDelta (G)$ (for short $\delta$ and $\varDelta$), respectively.

A proper edge coloring of a graph G is an assignment of colors to the edges such that adjacent edges receive distinct colors. The chromatic index $\chi ^{\prime }(G)$ is the minimum number of colors in a proper edge coloring of G. A strong edge-colouring (also called distance 2 edge-coloring) of G is a proper edge coloring of G, such that the edges of any path of length 3 use three different colors. We denote by $\chi _{s}^{\prime }(G)$ the strong chromatic index of G which is the smallest integer k such that G can be strongly edge-colored with k colors. The concept of strong edge-coloring was introduced by Fouquet and Jolivet in [6, 7] and can be used to model the conflict-free channel assignment in radio networks [14, 15].

In 1985, Erdős and Nešetřil [5] proposed the following conjecture concerning the upper bound on $\chi _{s}^{\prime }(G)$, and also provided an example to illustrate that this upper bound is sharp.

Conjecture 1

(Erdős and Nešetřil [5]) For every graph G,

$$\begin{aligned} \chi _{s}^{\prime }(G)\le \left\{ \begin{array}{lll} \frac{5}{4}\varDelta ^2, &{} &{} {if\,\varDelta \,is\,even,}\\ \frac{1}{4}(5\varDelta ^2-2\varDelta +1), &{} &{} {if\,\varDelta \,is\,odd.} \end{array} \right. \end{aligned}$$

Conjecture 1 was verified for graphs having $\varDelta \le 3$ [1, 10]. For $\varDelta =4$, an upper bound of 21 (recall that conjectured bound is 20 ) has been proved by Huang, Santana and Yu [11]. Moreover, Lv, Li and Yu [12] showed that Conjecture 1 is true for some special cases when for $\varDelta =4$. For sufficiently large $\varDelta$, using probabilistic techniques, Molloy and Reed in [13] proved that $\chi _s'(G) \le 1.998\varDelta (G)^2$. This bound is improved to $1.93\varDelta ^2$ by Bruhn and Joos [3], and very recently, is further improved to $1.835\varDelta ^2$ by Bonamy, Perrett, and Postle [2]. Currently the best known upper bound on the strong chromatic index of a graph with maximum degree $\varDelta$ is $1.772\varDelta ^2$, it was proved by Hurley, de Joannis de Verclos and Kang [8] in 2020.

A graph that contains no induced subgraph isomorphic to $K_{1,3}$ is said to be claw-free. Debski, Junosza-Szaniawski and Śleszyńska-Nowak [4] give the following upper bound for the strong chromatic index of claw-free graphs:

Theorem 1

(Debski, Junosza-Szaniawski and Śleszyńska-Nowak [4]) If G is a claw-free graph with maximum degree $\varDelta$, then $\chi _{s}^{\prime }(G)\le \frac{9}{8}\varDelta ^2+\varDelta$.

For claw-free subcubic graphs (claw-free graphs with $\varDelta \le 3$), we give the following somewhat stronger result.

Theorem 2

If G is a claw-free subcubic graph other than the prism graph, then $\chi _{s}^{\prime }(G)\le 8$, where the prism graph is the graph isomorphic to the configuration depicted in Figure 1.

Fig. 1

The prism graph $G^\prime$ has $\chi _{s}^{\prime }(G^\prime )=9$

Remark 1

Recall that when $\varDelta =3$, the upper bound in Conjecture 1 is 10, and the upper bound in Theorem 1 is $\frac{105}{8}$, while our bound is 8.

2 Preliminaries

We now introduce some notations used in the paper. For a graph G, a vertex is a k-vertex if it is of degree k. Similarly, we define i-cycle. A 3-cycle is called a triangle. For a vertex $v\in V(G)$, let $N_G(v)$ denote the set of all neighbors of v in G and let $\varGamma _G(v)$ denote the set of all edges incident to v in G. Denote by $SC(\varGamma _G(v))$ the set of colors used by edges in $\varGamma _G(v)$. Given edges $e_1$ and $e_2$ in G, we say that $e_1$ sees $e_2$ if either $e_1$ and $e_2$ are adjacent, or there is another edge $e_3$ adjacent to both $e_1$ and $e_2$. Denote by $[8]=\{1, 2,\ldots , 8\}$ the set of colors. A partial coloring of G is a strong edge-coloring of a proper subgraph of G. If $e=uv$ is an uncolored edge in a partial coloring of G, let $L_G(e)$ be the set of colors that is used on the edges incident to a vertex in $N_G(u)\cup N_G(v)$, and let $L^\prime _G(e)=[8]\backslash L_G(e)$. We write L(e) and $L^\prime (e)$ for $L_G(e)$ and $L^\prime _G(e)$, respectively, if it is clear from the context. Let d(u, v) be the distance between vertices u and v of G. For a cycle C, a vertex x and an edge e in G, let $d(C,x)=min_{u\in C}d(u,x)$ be the distance of the cycle C and the vertex x of G, and let $d(C,e)=min_{u\in C, v\in e}d(u,v)$ be the distance of the cycle C and the edge e of G. Let $K_4^*$ be the graph obtained from $K_4$ by subdividing one edge.

We will use the following well known result of Hall [9] in terms of systems of distinct representatives.

Theorem 3

(Hall [9]) Let $A_1 ,\ldots , A_n$ be n subsets of a set U. A system of distinct representatives of $\{A_1,\ldots , A_n\}$ exists if and only if for all $k, 1\le k\le n$ and every choice of subcollection of size k, $\{A_{i_1} ,\ldots , A_{i_k}\}$, we have $|A_{i_1}\cup \cdots \cup A_{i_k}|\ge k$.

3 Proof of Theorem 2

Let G be a counterexample to Theorem 2 with $|V(G)|+|E(G)|$ minimized. We will prove various statements about G. Clearly, G is connected.

Lemma 1

There is no 1-vertex in G.

Proof

Suppose that G contains 1-vertex v. Let u be the neighbor of v. By the minimality of G, $G^*=G-v$ has a strong edge-coloring with at most eight colors. The strong edge-coloring of $G^*$ is a partial coloring of G. G is claw-free so $|L^\prime (uv)|\ge 3$. Thus, we color uv to obtain a strong edge-coloring of G, a contradiction. $\square$

Lemma 2

There are no adjacent 2-vertices in G.

Proof

Suppose that G contains adjacent 2-vertices u and v. Let $N_G(u)=\{u^\prime ,v\}$ and $N_G(v)=\{v^\prime ,u\}$. Note that $u^\prime$ and $v^\prime$ may be the same vertex. By the minimality of G, $G^*=G-\{u,v\}$ has a strong edge-coloring with at most eight colors. The strong edge-coloring of $G^*$ is a partial coloring of G. G is a claw-free graph so $|L^\prime (uu^\prime )|\ge 3$, $|L^\prime (vv^\prime )|\ge 3$ and $|L^\prime (uv)|\ge 4$. Thus, we color $uu^\prime$, $vv^\prime$ and uv in turn to obtain a strong edge-coloring of G, a contradiction. $\square$

The following observation is true because G is claw-free.

Observation 1 Each 3-vertex is on at least one triangle in G.

Lemma 3

There is no 2-vertex in G.

Proof

Suppose that G contains 2-vertex v. Let $N_G(v)=\{u,w\}$. By Lemma 2, u and w are 3-vertices. By Observation 1, u and w are on triangles.

Assume that $uw\in E(G)$, by the minimality of G, $G^*=G-\{v\}$ has a strong edge-coloring with at most eight colors. The strong edge-coloring of $G^*$ is a partial coloring of G. Observe that $|L^\prime (uv)|\ge 3$ and $|L^\prime (wv)|\ge 3$. When we color uv, there are still two colors available for wv. Thus, we color uv and wv in turn to obtain a strong edge-coloring of G, a contradiction.

Assume that $uw\notin E(G)$. If $|N_G(u)\cap N_G(w)|\ge 2$, then $G\cong K_4^*$ and $\chi _{s}^{\prime }(G)=7$. If $|N_G(u)\cap N_G(w)|=1$, we use notations in Figure 2. By the minimality of G, $G^*=G-\{v\}$ has a strong edge-coloring $c^*$ with at most eight colors. The strong edge-coloring of $G^*$ is a partial coloring of G. Observe that $|L^\prime (uv)|\ge 1$ and $|L^\prime (wv)|\ge 1$. If $|L^\prime (uv)|\ge 2$, or $|L^\prime (wv)|\ge 2$, or $L^\prime (uv)\ne L^\prime (wv)$, we can assign distinct colors to uv and wv, and obtain a strong edge-coloring of G, a contradiction. Thus, we have $|L^\prime (uv)|=1$, $|L^\prime (wv)|=1$ and $L^\prime (uv)=L^\prime (wv)$. Without loss of generality, let $L^\prime (uv)=L^\prime (wv)=\{1\}$. Therefore, we may assume, without loss of generality, that $c^*(uu_1)=2$, $c^*(uu_2)=3$, $c^*(u_1u_2)=4$, $c^*(u_1u_3)=5$, $c^*(u_2u_4)=6$, $c^*(ww_1)=7$, $c^*(ww_2)=8$, $c^*(w_1w_2)=4$, $c^*(w_1w_3)=5$ and $c^*(w_2w_4)=6$. We claim that $7,8\in SC(\varGamma _G(u_3))$, if not, we can recolor $uu_1$ with 7 or 8, color uv with 2 and color vw with 1, and obtain a desired strong edge-coloring of G, a contradiction. Similar to the discussion above, we claim that $7,8\in SC(\varGamma _G(u_4))$, $2,3\in SC(\varGamma _G(w_3))$ and $2,3\in SC(\varGamma _G(w_4))$. Thus, we can recolor $uu_1$ and $ww_1$ with 1, color uv with 2 and color wv with 7, and obtain a strong edge-coloring of G, a contradiction. $\square$

Fig. 2

Illustrations of Lemma 3

Fig. 3

Illustrations of Lemma 4

Lemma 4

Each 3-vertex is on exactly one triangle in G.

Proof

By Observation 1, each 3-vertex is on at least one triangle. Suppose that a 3-vertex v is on two triangles $T_1=vv_1v_2$ and $T_2=vv_3v_2$, we use notations in Figure 3. By the minimality of G, $G^*=G-\{v,v_2\}$ has a strong edge-coloring with at most eight colors. The strong edge-coloring of $G^*$ is a partial coloring of G. Observe that $|L^\prime (vv_1)|\ge 4$, $|L^\prime (v_1v_2)|\ge 4$, $|L^\prime (vv_3)|\ge 4$, $|L^\prime (v_2v_3)|\ge 4$ and $|L^\prime (vv_2)|\ge 6$. Thus, we color $vv_1$, $v_1v_2$, $vv_3$, $v_2v_3$ and $vv_2$ in turn to obtain a strong edge-coloring of G, a contradiction. $\square$

Lemma 5

Suppose that $T_1=uvw$ and $T_2=u_1v_1u_2$ are two different triangles in G such that $vv_1\in E(G)$, then u (neither w) is not adjacent to $u_1$ nor $u_2$.

Proof

Without loss of generality, we assume that $uu_1\in E(G)$. Since G is not the prism graph, $u_2w\notin E(G)$, and we use notations in Figure 4. By the minimality of G, $G^*=G-\{u,v,u_1,v_1\}$ has a strong edge-coloring with at most eight colors. The strong edge-coloring of $G^*$ is a partial coloring of G. Observe that $|L^\prime (u_1u_2)|\ge 5$, $|L^\prime (v_1u_2)|\ge 5$, $|L^\prime (uw)|\ge 5$, $|L^\prime (vw)|\ge 5$, $|L^\prime (uu_1)|\ge 6$, $|L^\prime (vv_1)|\ge 6$, $|L^\prime (u_1v_1)|\ge 7$ and $|L^\prime (uv)|\ge 7$. Recall that $u_2w\notin E(G)$, edge $u_1u_2$ can not see edge vw in G. Note that $|L^\prime (u_1u_2)|\ge 5$, $|L^\prime (vw)|\ge 5$ and we have at most 8 different colors, so $L^\prime (u_1u_2)\cap L^\prime (vw)\ne \emptyset$. We color $u_1u_2$ and vw with the same color, and color $u_2v_1$, uw, $uu_1$, $vv_1$, $u_1v_1$ and uv in turn to obtain a strong edge-coloring of G, a contradiction. Thus, we obtain a strong edge-coloring of G, a contradiction. $\square$

Fig. 4

Illustrations of Lemma 5

Lemma 6

Let $v_1v_2v_3v_4v_5v_6$ be a 6-cycle without chord in G, and let $c^\prime$ be a partial coloring of G such that all uncolored edges are $v_1v_2$, $v_2v_3$, $v_3v_4$, $v_4v_5$, $v_5v_6$ and $v_6v_1$, and edge $v_1v_2$ can not see edge $v_4v_5$, edge $v_2v_3$ can not see edge $v_5v_6$, edge $v_3v_4$ can not see edge $v_6v_1$. If $|L^\prime (v_2v_3)|\ge 3$, $|L^\prime (v_4v_5)|\ge 3$, $|L^\prime (v_6v_1)|\ge 3$, $|L^\prime (v_1v_2)|\ge 4$, $|L^\prime (v_3v_4)|\ge 4$, and $|L^\prime (v_5v_6)|\ge 4$, then the partial coloring $c^\prime$ can be extended to a strong edge-coloring of G.

Proof

Notice that edge $v_1v_2$ can not see edge $v_4v_5$, edge $v_2v_3$ can not see edge $v_5v_6$, edge $v_3v_4$ can not see edge $v_6v_1$. If $L^\prime (v_1v_2)\cap L^\prime (v_4v_5)\ne \emptyset$. We color $v_1v_2$ and $v_4v_5$ with same color in $L^\prime (v_1v_2)\cap L^\prime (v_4v_5)$. Now $|L^\prime (v_2v_3)|\ge 2$, $|L^\prime (v_6v_1)|\ge 2$, $|L^\prime (v_3v_4)|\ge 3$, and $|L^\prime (v_5v_6)|\ge 3$, and we color $v_6v_1$, $v_2v_3$, $v_3v_4$ and $v_5v_6$ in this order to obtain a strong edge-coloring of G. Therefore, $L^\prime (v_1v_2)\cap L^\prime (v_4v_5)=\emptyset$. Similarly, we have $L^\prime (v_2v_3)\cap L^\prime (v_5v_6)=\emptyset$ and $L^\prime (v_6v_1)\cap L^\prime (v_3v_4)=\emptyset$. Let $A=\{v_1v_2$, $v_2v_3$, $v_3v_4$, $v_4v_5$, $v_5v_6,v_6v_1\}$, for any $S\subseteq A$, we have $|\cup _{e\in S} L^\prime (e)|\ge |S|$. By Theorem 3, we can assign distinct colors to $v_1v_2$, $v_2v_3$, $v_3v_4$, $v_4v_5$, $v_5v_6$ and $v_6v_1$. Thus, we obtain a strong edge-coloring of G. $\square$

Fig. 5

Illustrations of Lemma 7

Lemma 7

Suppose that $T_1=v_1v_2v_{12}$, $T_2=v_3v_4v_{34}$ and $T_3=v_5v_6v_{56}$ are three different triangles such that $v_2v_3\in E(G)$ and $v_4v_5\in E(G)$, then $v_1$ (neither $v_{12}$) is not adjacent to $v_6$ nor $v_{56}$.

Proof

Without loss of generality, we assume that $v_1v_6\in E(G)$. By Lemma 5, $v_{12}v_{34}\notin E(G)$, $v_{34}v_{56}\notin E(G)$ and $v_{56}v_{12}\notin E(G)$, and we use notations in Figure 5. By the minimality of G, $G^*=G-\{v_1,v_2,v_3,v_4,v_5,v_6\}$ has a strong edge-coloring with at most eight colors. The strong edge-coloring of $G^*$ is a partial coloring of G. Observe that $|L^\prime (v_1v_{12})|\ge 5$, $|L^\prime (v_2v_{12})|\ge 5$, $|L^\prime (v_3v_{34})|\ge 5$, $|L^\prime (v_4v_{34})|\ge 5$, $|L^\prime (v_5v_{56})|\ge 5$, $|L^\prime (v_6v_{56})|\ge 5$, $|L^\prime (v_2v_3)|\ge 6$, $|L^\prime (v_4v_5)|\ge 6$, $|L^\prime (v_6v_1)|\ge 6$, $|L^\prime (v_1v_2)|\ge 7$, $|L^\prime (v_3v_4)|\ge 7$, and $|L^\prime (v_5v_6)|\ge 7$.

Note that $L^\prime (v_1v_{12})=L^\prime (v_2v_{12})$, $L^\prime (v_3v_{34})=L^\prime (v_4v_{34})$ and $L^\prime (v_5v_{56})=L^\prime (v_6v_{56})$. Beacause $L^\prime (v_1v_{12})$ and $L^\prime (v_3v_{34})$ are 5-element subsets of 8-element set their intersection has at least 2 elememnts, denote them by $\alpha _1$, $\alpha _2$, that is $\{\alpha _1,\alpha _2\}\subset L^\prime (v_1v_{12})\cap L^\prime (v_3v_{34})$. Similarly, we let $\{\beta _1,\beta _2\}\subset L^\prime (v_1v_{12})\cap L^\prime (v_5v_{56})$ and $\{\gamma _1,\gamma _2\}\subset L^\prime (v_3v_{34})\cap L^\prime (v_5v_{56})$. Recall that $v_{12}v_{34}\notin E(G)$, $v_{34}v_{56}\notin E(G)$ and $v_{56}v_{12}\notin E(G)$, then edge $v_1v_{12}$ can not see edges $v_3v_{34}$, $v_4v_{34}$, $v_5v_{56}$, and edge $v_2v_{12}$ can not see edges $v_4v_{34}$, $v_5v_{56}$, $v_6v_{56}$, and edge $v_3v_{34}$ can not see edges $v_1v_{12}$, $v_5v_{56}$, $v_6v_{56}$, and edge $v_4v_{34}$ can not see edges $v_6v_{56}$, $v_1v_{12}$, $v_2v_{12}$.

If $\{\alpha _1,\alpha _2\}\cap \{\beta _1,\beta _2\}\ne \emptyset$, we color $v_1v_{12}$, $v_3v_{34}$ and $v_5v_{56}$ with same color in $\{\alpha _1,\alpha _2\}\cap \{\beta _1,\beta _2\}$, and color $v_2v_{12}$, $v_4v_{34}$ and $v_6v_{56}$ in this order. Now, we have $|L^\prime (v_2v_3)|\ge 3$, $|L^\prime (v_4v_5)|\ge 3$, $|L^\prime (v_6v_1)|\ge 3$, $|L^\prime (v_1v_2)|\ge 4$, $|L^\prime (v_3v_4)|\ge 4$, and $|L^\prime (v_5v_6)|\ge 4$. By Lemma 6, we obtain a strong edge-coloring of G, a contradiction.

If $\{\beta _1,\beta _2\}\cap \{\gamma _1,\gamma _2\}\ne \emptyset$, we color $v_1v_{12}$, $v_3v_{34}$ and $v_5v_{56}$ with same color in $\{\beta _1,\beta _2\}\cap \{\gamma _1,\gamma _2\}$, and color $v_2v_{12}$, $v_4v_{34}$ and $v_6v_{56}$ in this order. Now, we have $|L^\prime (v_2v_3)|\ge 3$, $|L^\prime (v_4v_5)|\ge 3$, $|L^\prime (v_6v_1)|\ge 3$, $|L^\prime (v_1v_2)|\ge 4$, $|L^\prime (v_3v_4)|\ge 4$, and $|L^\prime (v_5v_6)|\ge 4$. By Lemma 6, we obtain a strong edge-coloring of G, a contradiction.

If $\{\alpha _1,\alpha _2\}\cap \{\gamma _1,\gamma _2\}\ne \emptyset$, we color $v_1v_{12}$, $v_3v_{34}$ and $v_5v_{56}$ with same color in $\{\alpha _1,\alpha _2\}\cap \{\gamma _1,\gamma _2\}$, and color $v_2v_{12}$, $v_4v_{34}$ and $v_6v_{56}$ in this order. Now, we have $|L^\prime (v_2v_3)|\ge 3$, $|L^\prime (v_4v_5)|\ge 3$, $|L^\prime (v_6v_1)|\ge 3$, $|L^\prime (v_1v_2)|\ge 4$, $|L^\prime (v_3v_4)|\ge 4$, and $|L^\prime (v_5v_6)|\ge 4$. By Lemma 6, we obtain a strong edge-coloring of G, a contradiction.

Therefore, $\{\alpha _1,\alpha _2\}\cap \{\beta _1,\beta _2\}=\emptyset$, $\{\beta _1,\beta _2\}\cap \{\gamma _1,\gamma _2\}=\emptyset$ and $\{\alpha _1,\alpha _2\}\cap \{\gamma _1,\gamma _2\}=\emptyset$. Thus, we color $v_1v_{12}$ and $v_3v_{34}$ with $\alpha _1$, color $v_2v_{12}$ and $v_5v_{56}$ with $\beta _1$, and color $v_4v_{34}$ and $v_6v_{56}$ with $\gamma _1$. Now, we have $|L^\prime (v_2v_3)|\ge 3$, $|L^\prime (v_4v_5)|\ge 3$, $|L^\prime (v_6v_1)|\ge 3$, $|L^\prime (v_1v_2)|\ge 4$, $|L^\prime (v_3v_4)|\ge 4$, and $|L^\prime (v_5v_6)|\ge 4$. By Lemma 6, we obtain a strong edge-coloring of G, a contradiction. $\square$

Proof of Theorem 2:

By Lemmas 1, 3 and 4, G is 3-regular and each 3-vertex is on exactly one triangle in G. Let $C=uvw$ be a triangle and $N_G(u)=\{w, v, u_1\}$, $N_G(v)=\{w,u,v_1\}$, $N_G(w)=\{u,v,w_1\}$. Let $C_1=u_1u_2u_3$ be the triangle where $u_1$ is located, $C_2=v_1v_2v_3$ be the triangle where $v_1$ is located and $C_3=w_1w_2w_3$ be the triangle where $w_1$ is located. By Lemmas 4 and 5, $V(C_1)\cap V(C_2)=\emptyset$, $V(C_1)\cap V(C_3)=\emptyset$ and $V(C_2)\cap V(C_3)=\emptyset$. We use notations in Figure 6. For C, $C_1$ and $C_3$, we have $u_2w_2\notin E(G)$, $u_2w_3\notin E(G)$ by Lemma 7. For C, $C_2$ and $C_3$, we have $v_2w_2\notin E(G)$, $v_2w_3\notin E(G)$ by Lemma 7. For C, $C_1$ and $C_2$, we have $u_2v_2\notin E(G)$ by Lemma 7. Therefore, edge $ww_1$ can not see edges $u_1u_2$, $v_1v_2$, and edge $v_1v_2$ can not see edges $u_1u_2$, $ww_1$.

Precolor $u_1u_2$, $v_1v_2$ and $ww_1$ with the same color. Color in a greedy way edges of $G-\{u,v\}$ in the decresing order with the respect to the disctance from the cycle C, that is, if $d(C,e_1)\ge d(C, e_2)$, then edge $e_1$ precedes edge $e_2$ (if egde $e_1$ has two vertecies in distance k and $k+1$ and edge $e_2$ has two vertices both at distance k form C, we let $e_1$ proceeds $e_2$ in the ordering). For each $e=xy$ in the order with $d(C,x)\ge d(C,y)\ge 2$, y is adjacent to some vertex z with $d(C,z)<d(C,y)$. So the three edges incident with z are after the edge e in the order. Clearly, at least two of the three edges at z are not precolored, thus e sees at least two uncolored edges in $G-\{u,v\}$. On the other hand, by Lemma 4, each 3-vertex is on exactly one triangle in G. Therefore, e sees at most 7 different colors, and thus can be colored. For each $e=xy$ in the order with $d(C,x)\ge d(C,y)=1$, then $e\in \{w_3w_1,w_2w_1,u_3u_1,v_3v_1\}$, and note that e sees at most 7 different colors, and thus can be colored.

Fig. 6

Illustrations of Proof of Theorem 2

Now $|L^\prime (uu_1)|\ge 3$, $|L^\prime (vv_1)|\ge 3$, $|L^\prime (uw)|\ge 4$, $|L^\prime (wv)|\ge 4$ and $|L^\prime (uv)|\ge 5$. Thus, we can color $uu_1$, $vv_1$, uw, wv and uv in this order to obtain a strong edge-coloring of G, which gives a contradition with the definition of G. This completes the proof of Theorem 2. $\square$

4 Final Remark

In this note, we have proved that if G is a claw-free subcubic graph other than the prism graph, then $\chi _{s}^{\prime }(G)\le 8$. By the aid of computer experiment, for $n\le 20$, we find the claw-free subcubic graph $G^{\prime \prime }$ with $\chi _{s}^{\prime }(G^{\prime \prime })=7$ (see Figure 7), and not find the claw-free subcubic graph G with $\chi _{s}^{\prime }(G)=8$. Thus we leave the following problem for further study.

Fig. 7

The claw-free subcubic graph $G^{\prime \prime }$ with $\chi _{s}^{\prime }(G^{\prime \prime })=7$

Problem 1

If G is a claw-free subcubic graph other than the prism graph, then $\chi _{s}^{\prime }(G)\le 7$.