A note on strong edge-coloring of claw-free cubic graphs

Abstract

A strong edge-coloring of a graph G is an edge-coloring of G such that any two edges that are either adjacent to each other or adjacent to a common edge receive distinct colors. The strong chromatic index of G, denoted by $\chi '_s(G)$, is the minimum number of colors needed to guarantee that G admits a strong edge-coloring. For any integer $n\ge 3$, let $H_n$ denote the n-prism (i.e., the Cartesian product $C_n\square K_2$) and $H_n^{\Delta }$ the graph obtained from $H_n$ by replacing each vertex with a triangle. Recently, Lin and Lin (2022) asked whether $\chi '_s(H_n^{\Delta })=6$ for any $n\ge 3$. In this short note, we answer this question in the affirmative.

1 Introduction

In this note, we only consider finite simple graphs. A strong k-edge-coloring of a graph G is a mapping $\phi :E(G)\rightarrow \{1,2,\ldots ,k\}$ such that if any two edges e and f are either adjacent to each other or adjacent to a common edge in G, then $\phi (e)\ne \phi (f)$. The strong chromatic index of G, denoted by $\chi '_s(G)$, is the minimum integer k for which G has a strong k-edge-coloring. This concept was first introduced by Fouquet and Jolivet [8, 9] and was used to solve a problem involving radio networks and their frequencies (more details on this application can be found in [18, 19]).

A well-known conjecture of Erdős and Nešetřil [5, 6] states that for any graph G with maximum degree $\Delta$, $\chi '_s(G)\le \frac{5}{4}\Delta ^2$ if $\Delta$ is even and $\chi '_s(G)\le \frac{5}{4}\Delta ^2-\frac{1}{2}\Delta +\frac{1}{4}$ if $\Delta$ is odd. This conjecture is still wide open. For graphs with $\Delta \le 3$ (such graphs are often referred to as subcubic graphs), the conjecture was confirmed by Andersen [1], and independently by Horák, Qing and Trotter [11]. For graphs with $\Delta =4$, an upper bound of 21 was proved by Huang, Santana and Yu [12] (note that the conjectured bound is 20). For sufficiently large $\Delta$, Molloy and Reed [17] showed that $\chi '_s(G)\le 1.998\Delta ^2$ by applying probabilistic techniques. This was later improved to $1.93\Delta ^2$ by Bruhn and Joos [3], and then to $1.835\Delta ^2$ by Bonamy, Perrett and Postle [2]. The current best known upper bound is $1.772\Delta ^2$, which was recently derived by Hurley, de Joannis de Verclos and Kang [13].

The strong chromatic index of planar graphs has been intensively studied. Faudree et al. [7] proved that $\chi '_s(G)\le 4\Delta +4$ for any planar graph G with maximum degree $\Delta$, and showed that there exists a planar graph G with $\chi '_s(G)= 4\Delta -4$ for any $\Delta \ge 2$. Hocquard, Ochem and Valicov [10] proved that $\chi '_s(G)\le 3\Delta -3$ for any outerplanar graph G with maximum degree $\Delta \ge 3$, and constructed an example showing that the upper bound is the best possible. Confirming a conjecture of Faudree et al. [7], Kostochka et al. [14] proved that $\chi '_s(G)\le 9$ for any subcubic planar graph G. For planar graphs with maximum degree 4, an upper bound of 19 was obtained by Wang et al. [20].

A graph is said to be claw-free if it does not contain an induced subgraph isomorphic to $K_{1,3}$. Dȩbski, Junosza-Szaniawski and Śleszyńska-Nowak [4] showed that $\chi '_s(G)\le \frac{9}{8}\Delta ^2+\Delta$ for any claw-free graph G with maximum degree $\Delta$. This verified the aforementioned conjecture of Erdős and Nešetřil for claw-free graphs with maximum degree at least 12. For any integer $n\ge 3$, the n-prism $H_n$ is the Cartesian product $C_n\square K_2$. In 2022, Lv, Li and Zhang [16] proved that $\chi '_s(G)\le 8$ for any connected claw-free subcubic graph G other than the 3-prism, and asked whether the upper bound 8 can be improved to 7. Very recently, Lin and Lin [15] solved this problem and constructed infinitely many connected claw-free subcubic graphs with the strong chromatic index attaining the upper bound 7.

Theorem 1.1

(Lin and Lin [15]) If G is a connected claw-free subcubic graph not isomorphic to the 3-prism, then $\chi '_s(G)\le 7$.

It is easy to observe that if G is a connected claw-free cubic graph, then $\chi '_s(G)\ge 6$. Hence, Theorem 1.1 implies that $\chi '_s(G)\in \{6,7\}$ for any connected claw-free cubic graph G other than the 3-prism.

Let $H_n^{\Delta }$ denote the graph obtained from the n-prism $H_n$ by replacing each vertex with a triangle. It is clear that $H_n^{\Delta }$ is a connected claw-free cubic graph. At the end of their paper, Lin and Lin [15] suggested three questions for future research, one of which is as follows.

Question 1.2

(Lin and Lin [15]) Is it true that $\chi '_s(H_n^{\Delta })=6$ for any integer $n\ge 3$?

The main objective of this short note is to give an affirmative answer to this question.

2 The proof

In this section, we prove the following theorem which answers Question 1.2 affirmatively.

Theorem 2.1

$\chi '_s(H_n^{\Delta })=6$ for any integer $n\ge 3$.

Proof For the sake of simplicity, suppose that $V(H_n^{\Delta })=\{u_i,v_i,w_i,x_i,y_i,z_i:1\le i\le n\}$ and $E(H_n^{\Delta })=\{u_iv_i,v_iu_{i+1},u_iw_i,v_iw_i,x_iy_i,y_ix_{i+1}, x_iz_i,y_iz_i,w_iz_i:1\le i\le n\}$, where the subscripts are taken modulo n. An illustration is depicted in Fig. .

Fig. 1

The graph $H_{n}^{\Delta }$

As we mentioned in the Introduction, it is easy to observe that $\chi '_s(H_n^{\Delta })\ge 6$. (One can notice that for each $i=1,2,\ldots ,n$, the six edges incident to $u_i,v_i$ or $w_i$ must be colored with distinct colors.) Hence to prove Theorem 2.1, it suffices to show that $H_n^{\Delta }$ admits a strong 6-edge-coloring which implies that $\chi '_s(H_n^{\Delta })\le 6$. We consider two cases according to the parity of n.

Case 1 n is even.

Fig. 2

A strong 6-edge-coloring of $H_{2k}^{\Delta }$

Fig. 3

A strong 6-edge-coloring of $H_{3}^{\Delta }$

Fig. 4

A strong 6-edge-coloring of $H_{2k+1}^{\Delta }$

Then $n=2k$ for some integer $k\ge 2$. We define an edge-coloring $\phi$ of $H_{2k}^{\Delta }$ as follows:

• (1.1) for each $i=1,2,\ldots ,2k$, let $\phi (u_iw_i)=1$, $\phi (v_iw_i)=2$, $\phi (x_iz_i)=3$ and $\phi (y_iz_i)=4$;

• (1.2) for each $i=1,3,\ldots ,2k-1$, let $\phi (w_iz_i)=5$, $\phi (u_iv_i)=\phi (x_iy_i)=6$, $\phi (v_iu_{i+1})=3$ and $\phi (y_ix_{i+1})=1$; and

• (1.3) for each $i=2,4,\ldots ,2k$, let $\phi (w_iz_i)=6$, $\phi (u_iv_i)=\phi (x_iy_i)=5$, $\phi (v_iu_{i+1})=4$ and $\phi (y_ix_{i+1})=2$.

See Fig.  for an illustration. It is easy to verify that $\phi$ is a strong 6-edge-coloring of $H_{2k}^{\Delta }$.

Case 2 n is odd.

If $n=3$, then a strong 6-edge-coloring of $H_3^{\Delta }$ is given in Fig. . So we may assume that $n\ge 5$, and hence $n=2k+1$ for some integer $k\ge 2$. We define an edge-coloring $\psi$ of $H_{2k+1}^{\Delta }$ as follows:

• (2.1) for each $i=1,2,\ldots ,2k+1$, let $\psi (u_iw_i)=1$, $\psi (v_iw_i)=2$, $\psi (x_iz_i)=3$ and $\psi (y_iz_i)=4$;

• (2.2) for each $i=1,3,\ldots ,2k-1$, let $\psi (w_iz_i)=5$, $\psi (u_iv_i)=\psi (x_iy_i)=6$, $\psi (v_iu_{i+1})=3$ and $\psi (y_ix_{i+1})=1$;

• (2.3) for each $i=2,4,\ldots ,2k-2$, let $\psi (w_iz_i)=6$, $\psi (u_iv_i)=\psi (x_iy_i)=5$, $\psi (v_iu_{i+1})=4$ and $\psi (y_ix_{i+1})=2$; and

• (2.4) for the remaining uncolored edges, let $\psi (x_{2k+1}y_{2k+1})=1$, $\psi (x_{2k}y_{2k})=\psi (y_{2k+1}x_1)=2$, $\psi (u_{2k+1}v_{2k+1})=3$, $\psi (u_{2k}v_{2k})=\psi (v_{2k+1}u_1)=4$, $\psi (w_{2k}z_{2k})=\psi (w_{2k+1}z_{2k+1})=5$, and $\psi (v_{2k}u_{2k+1})=\psi (y_{2k}x_{2k+1})=6$.

Please refer to Fig.  for a detailed illustration. One can easily check that $\psi$ is a strong 6-edge-coloring of $H_{2k+1}^{\Delta }$. This completes the proof of the theorem. $\square$