The strong chromatic index of graphs with edge weight eight

Abstract

The edge weight of a graph G is defined to be $\max \{d_G(u) + d_G(v): uv \in E(G)\}$. The strong chromatic index of a graph is the minimum value of k such that the edge set of G can be partitioned into k induced matchings. In this article, we prove that the strong chromatic index of a graph with edge weight eight is at most 21.

1 Introduction

All graphs in this article are simple and undirected. A strong edge-coloring of a graph G, first introduced by  Fouquet and Jolivet (1983), is a proper edge-coloring of G such that any two edges joined by another one have distinct colors. Clearly, every coloring class is an induced matching of G. The minimum number of colors needed in a strong edge-coloring is called the strong chromatic index, denoted by $\chi _s^{\prime }(G)$.

Let G be a graph and let $\Delta$ be the maximum degree of G. In 1989, Erdős and Nešetřil (1989) conjectured that $\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. They also found a class of graphs that can reach these upper bounds. Since then, there have been many progress on the conjecture, especially for various classes of sparse graphs, like planar graphs; k-degenerate graphs, bipartite graphs, graphs with small maximum average degree, and so on. The strong chromatic index on some special graphs have also been studied, such as unit distance graph (Debski 2019), and generalized Petersen graph (Yang and Wu 2018). For an overview of the strong edge-coloring, we refer the reader to the survey (Deng et al. 2019).

The edge weight of a graph G is defined to be $\max \{d_G(u)+d_G(v)|uv \in E(G)\}$. Note that, for every edge $uv \in E(G)$, the edges incident with u or v must receive different colors in a strong edge-coloring. So $\chi _s^{\prime }$ is bounded below by the edge weight minus one. It would be interesting if one can find a relationship between the edge weight and an upper bound for $\chi _s^{\prime }$. The first such result was proved by  Wu and Lin (2008) in 2008.

Theorem 1.1

(Wu and Lin (2008)) If G is a connected graph with edge weight at most 5. Then either $\chi _s'(G)\le 6$ or G is isomorphic to the graph obtained from $C_5$ by adding a new vertex connecting to a pair of nonadjacent vertices.

Recently, Chen et al. (2020) proved the following theorem:

Theorem 1.2

(Chen et al. (2020)) Let G be a graph.

• (1) if the edge weight of G is at most 6, then $\chi _s ^{\prime } (G) \le 10$;

• (2) if the edge weight of G is at most 7, then $\chi _s ^{\prime }(G) \le 15$.

They gave a graph with edge weight 7 and strong chromatic index 13, which suggests that the bound of 15 may not be tight. In this article, we study graphs with edge weight 8 and prove the following result.

Theorem 1.3

For any graph G with edge weight 8, $\chi _s'(G)\le 21$.

Fig. 1

A graph with edge weight 8 and strong chromatic index 20

Note that the graph in Fig.  1 given by Erdős and Nešetřil (1989) has edge weight 8 and strong chromatic index 20. No known example of graphs with edge weight 8 would require 21 colors. We strongly believe that the following conjecture should be true.

Conjecture 1.4

For any graph G with edge weight 8, $\chi _s'(G)\le 20$.

The proof of our result relies heavily on the following result of  Huang et al. (2018).

Theorem 1.5

(Huang et al. (2018)) If G is a graph with maximum degree 4, then $\chi _s ^{\prime } (G) \le 21$.

Note that every 4-regular graph has edge weight 8, so our result is a natural extension of Theorem 1.5. Likewise, Conjecture 1.4 is a non-trivial extension of Erdős and Nešetřil’s Conjecture for $\Delta =4$. While it might be true that Conjecture 1.4 would follow from Erdős and Nešetřil’s Conjecture, the proof used in this article does not provide a direct link between these two conjectures, as we require the use of 21 colors in a number of important steps.

2 Proof of Theorem 1.3

We will use k-vertex (resp. $k^-$-vertex, $k^+$-vertex) to denote a vertex of degree k (resp. at most k; at least k). For $v \in V(G)$, we use N(v) to denote the set of neighbors of v. For two edges e and $e'$, we say that esees$e'$ if they are incident with a common vertex or adjacent to a common edge. Apparently, such two edges must be assigned different colors in any strong edge-colorings of G.

From now on, we assume that G is a minimal counterexample to Theorem 1.3, that is, G has edge weight 8, $\chi _s^{\prime } (G) \ge 22$, and |V(G)| as small as possible. A partial strong edge-coloring of G is a proper edge-coloring of a subgraph $G^{\prime }$ of G with at most 21 colors such that any two edges that can see each other in G receive distinct colors. We will show that a certain partial strong edge-coloring of G can be extended to a strong edge-coloring of G. We denote by C(e) the set of colors that are available for $e\in E(G)-E(G^{\prime })$ and we let $c(e) = |C(e)|$. By a good coloring, we mean a strong edge-coloring using at most 21 colors.

Next we prove some basic properties of G.

Lemma 2.1

The minimum degree of G is at least 3.

Proof

Assume that there exists a vertex $v\in E(G)$ with $d_G(v) \le 2$. If $d_G(v)=1$ and $v'$ is the only neighbor of v, then the edge $vv^{\prime }$ can see at most 12 edges in $G-v$. So a good coloring of $G -v$ can be easily extended to a good coloring of G, a contradiction. If $d_G(v)=2$ and $v^{\prime }$ and $v^{\prime \prime }$ are the two neighbors of v, then each of the edges $vv^{\prime }$ and $vv^{\prime \prime }$ can see at most 17 edges in $G-v$. So a good coloring of $G-v$ can again be easily extended to a good coloring of G, a contradiction.$\square$

It follows immediately that $d_G(v)\in \{3,4,5\}$ for any $v\in V(G)$.

Lemma 2.2

A 3-vertex can not be adjacent to a 3-vertex.

Proof

Let v be a 3-vertex with neighbor set $\{v_1,v_2,v_3\}$. Assume without loss of generality that $d_G(v_1)=3$. Then the edge $vv_1$ can see at most 18 edges of $G-v$, there are at least three colors available for the edge $vv_1$, we color it with one of the colors. Now each of the edges $vv_2$, and $vv_3$ can see at most 19 edges, and there are at least 2 colors for each of them, so a good coloring of $G-v$ can be extended to a good coloring of G, a contradiction.

The case in which one of $v_2$ and $v_3$ is a 3-vertex is done in a similar manner. $\square$

Lemma 2.3

Every 3-vertex is adjacent to at least one 5-vertex.

Proof

Let v be a 3-vertex with neighbor set $\{v_1,v_2,v_3\}$. If none of them is a 5-vertex, then by Lemma 2.2, they must all be 4-vertices. Then each of the edges $vv_1$, $vv_2$, and $vv_3$ can see at most 18 edges of $G-v$, therefore, there are at least 3 colors available for $vv_1$, $vv_2$, and $vv_3$. So a good coloring of $G - v$ can be extended to a good coloring of G. $\square$

By Theorem 1.5, we may assume that G has at least one 5-vertex.

Let $G'$ be a subgraph of G with $|V(G')| < |V(G)|$. Suppose that G has a strong partial edge-coloring $\phi$ on $G^{\prime }$. In order to extend $\phi$ to a good coloring of G, we construct a bipartite graph $B=B[X,Y]$ with bipartition (X, Y), where a vertex $x\in X$ corresponds to an edge x in $E(G)- E(G^{\prime })$, $Y=[21]$ is the set of all 21 colors, and a vertex $x\in X$ is adjacent to a vertex $y \in Y$ if and only if the color y is available for the edge x. By the construction of B, if B has a matching M that covers X, then we color each edge of $E(G)-E(G^{\prime })$ with the color that is adjacent to it in M, hence the coloring $\phi$ of $G'$ can be extended to a good coloring of G. The edges in X will be ordered by $e_0$, $e_1$, $\ldots$, $e_k$. The degree sequence ofX in B, denoted by $d_B(X)$, is the sequence $(d_0, d_1, \ldots , d_k)$ where $d_i = d_B (e_i)$ for $0 \le i \le k$. That is, $d_i$ is the number of available colors for the edge $e_i$. Let $S=(s_0, s_1, \ldots , s_k)$ and $S'=(s'_0, s'_1, \ldots , s'_k)$ be two sequences of the same length. We say that S dominates $S'$ if for each $i \in \{0, 1, \ldots , k\}$, $s_i \ge s^{\prime }_i$. We need the well-known Hall’s Theorem  (Hall 1935) in our proofs.

Theorem 2.4

A bipartite graph $B=B[X,Y]$ has a matching that covers every vertex of X if and only if $|N_B(S)|\ge |S|$ for all $S\subseteq X$, where $N_B(S)$ is the set of all neighbors of vertices in S.

Let v be a 5-vertex of G and let $N(v) = \{v_1,v_2,v_3,v_4.v_5\}$. Note that each of $v_i$, $1 \le i \le 5$ is a 3-vertex. For each $1 \le i \le 5$, we use $v_i ^{\prime }$ and $v_i ^{\prime \prime }$ to denote the neighbors of $v_i$ other than v. We shall label the edges incident to v, $v_1$, or $v_2$ as shown in Fig. 2.

Fig. 2

A 5-vertex v and its neighbors

Lemma 2.5

For any $\{i,j\} \subset \{1,2,3,4,5\}$, we have that $v_iv_j\notin E(G)$.

Proof

Suppose otherwise. By symmetry, we may assume that $v_1v_2 \in E(G)$. Let $G^{\prime }=G-v$. Then each of the edges $vv_1$ and $vv_2$ can see at most 13 edges of $G^{\prime }$; and each of the edges $vv_3$, $vv_4$, and $vv_5$ can see at most 17 edges of $G^{\prime }$; we can first color $vv_3$, $vv_4$, $vv_5$, then color $vv_1$ and $vv_2$ to extend a good coloring of $G^{\prime }$ to a good coloring of G; a contradiction. $\square$

Lemma 2.6

For any $\{i,j\} \subset \{1,2,3,4,5\}$, $N(v_i)\cap N(v_j)=\{v\}$.

Proof

By symmetry, we only need show that $v_1$ and $v_2$ have no common neighbor other than v. It is easy to see that we have the following three cases.

• (1) $v_1'=v_2'$ and $v_1''=v_2''$.

  In this case, we consider the subgraph $G-v$. Then each of $vv_1$ and $vv_2$ can see at most 16 edges of $G-v$; each of $vv_3$, $vv_4$, and $vv_5$ can see at most 18 edges of $G-v$. We can first color $vv_3$, $vv_4$, and $vv_5$, then color $vv_1$ and $vv_2$ to extend a good coloring of $G-v$ to a good coloring of G; a contradiction.

• (2) $v_1'=v_2'$ and $v_1''v_2''\in E(G)$.

  In this case, by Lemma 2.2, we have that $d_G(v_1'')\ne 3$, $d_G(v_2'')\ne 3$. By Lemma 2.1, $d(v)\in \{3,4,5\}$ for any $v\in V(G)$. If $d_G(v_1'')=5$, since $v_1''v_2''\in E(G)$, $d_G(v_2'')=3$, a contradiction. Therefore, $d_G(v_1'')=4$. Similarly, $d_G(v_2'')=4$. We again consider the subgraph $G-v$. Then each of $vv_1$ and $vv_2$ can see at most 16 edges of $G-v$; each of $vv_3$, $vv_4$, and $vv_5$ can see at most 18 edges of $G-v$. We can first color $vv_3$, $vv_4$, and $vv_5$, then color $vv_1$ and $vv_2$ to extend a good coloring of $G-v$ to a good coloring of G; a contradiction.

• (3) $v_1'=v_2'$ and the edges $v_1v_1^{\prime \prime }$ and $v_2v_2^{\prime \prime }$ do not see each other.

  In this case, we will choose $G'=G-\{v,v_1,v_2\}$ and construct the bipartite graph B[X, Y], where $X=E(G)-E(G')=\{e_1, e_2, \ldots , e_9\}$ and $Y=[21]$. Then by calculating the least number of available colors for each edge in X, we have the degree sequence $d_B(X)$ dominates the sequence (8, 6, 8, 6, 8, 8, 7, 7, 7). For any $S\subseteq X$ with $|S|\le 8$, we have $|N_B(S)|\ge |S|$. Now if $|N_B(X)| \ge 9$, then by Hall’s theorem, there exists a matching that covers X, which implies a good coloring of $G'$ can be extended to a good coloring of G. So we may assume that $|N_B(X)|=8$. If $C(e_2)\cap C(e_4)=\emptyset$, $|C(e_2)\cup C(e_4)|\ge 12$, then $|N_B(X)|\ge 12\ge |X|=9$, contrary to our assumption. So $C(e_2) \cap C(e_4) \ne \emptyset$. Since $e_2$ and $e_4$ do not see each other, we may color them with one color. Therefore the degree sequence $d_B(X-\{e_2,e_4\})$ dominates (7, 7, 7, 7, 6, 6, 6). So for any $S\subseteq (X-\{e_2,e_4\})$, we have that $|N_B(S)|\ge |S|$, by Hall’s theorem, there exists a matching that covers $X - \{e_2, e_4\}$, thus a good coloring of $G'$ can be extended to a good coloring of G; a contradiction.

Therefore $v_1$ and $v_2$ have no common neighbor other than v, that is, $N(v_1)\cap N(v_2)=\{v\}$. $\square$

Lemma 2.7

Neither $v_1v_1^{\prime }$ nor $v_1 v_1 ^{\prime \prime }$ can see the edges $v_2v_2^{\prime }$ or $v_2v_2^{\prime \prime }$.

Proof

Suppose otherwise. By symmetry, we may assume that the edge $v_1v_1^{\prime }$ can see the edge $v_2v_2^{\prime }$, that is, $v_1 ^{\prime }v_2 ^{\prime } \in E(G)$. By Lemma 2.6, $v_1^{\prime } , v_1^{\prime \prime } \notin \{v_2 ^{\prime }, v_2 ^{\prime \prime }\}$. Since G has no adjacent 3-vertices, both $v_1^{\prime }$ and $v_2^{\prime }$ are 4-vertices. We consider the following two cases:

Case 1: the edge $v_1v_1^{\prime }$ also sees the edge $v_2v_2^{\prime \prime }$.

In this case, we have that $v_1 ^{\prime }v_2 ^{\prime \prime } \in E(G)$ and $d_G(v_2^{\prime \prime }) =4$. Consider the subgraph $G-v$. Then $vv_1$ sees at most 17 edges of $G-v$; $vv_2$ sees at most 16 edges of $G-v$; and each of the edges $vv_3$, $vv_4$, and $vv_5$ sees at most 18 edges of $G-v$. So we may color the edges in $E(G) - E(G')$ in the following order $vv_3$, $vv_4$, $vv_5$, $vv_1$, $vv_2$. This way we can extend a good coloring of $G'$ to a good coloring of G; a contradiction.

Case 2: the edge $v_1v_1^{\prime }$ does not see the edge $v_2v_2^{\prime \prime }$.

In this case, we will choose $G'=G-\{v,v_1,v_2\}$ and construct the bipartite graph B[X, Y], where $X=E(G)-E(G')=\{e_1, e_2, \ldots , e_9\}$ and $Y=[21]$. Then the degree sequence $d_B(X)$ dominates (6, 6, 6, 6, 8, 8, 7, 7, 7). Note that, for any proper subset S of X, we have that $|N_B(S)| \ge |S|$. So by Hall’s Theorem, if $|N_B(X)| \ge 9$, then there exists a matching that covers X, and thus, a good coloring of $G'$ can be extended to a good coloring of G; a contradiction. So we may assume that $|N_B(X)| = 8$. Since the edge $e_1 =v_1 v_1^{\prime }$ does not see the edge $e_4 = v_2 v_2^{\prime \prime }$, we may color $e_1$ and $e_4$ with the same color, now the degree sequence for the remaining edges dominates (5, 5, 7, 7, 6, 6, 6). Again by Hall’s theorem, a good coloring of $G'$ can be extended to a good coloring of G, a contradiction. $\square$

Now we are ready to complete the proof for Theorem 1.3. Let $G'=G-\{v,v_1,v_2\}$ and we construct the bipartite graph B[X, Y], where $X=E(G)-E(G')=\{e_1, e_2, \ldots , e_9\}$ and $Y=[21]$. Then the degree sequence $d_B(X)$ dominates (5, 5, 5, 5, 7, 7, 7, 7, 7). Note that for any $S\subseteq X$ with $|S|\le 7$, we have that $|N_B(S)|\ge |S|$. So we may assume that there exists an $S_0 \subseteq X$ with $|S_0| =8$ or 9 such that $|N_B(S_0)| < |S_0|$.

First assume that $|S_0|=9$, that is, $S_0=X$. Then $7\le |N_B(X)|\le 8$. Note that $|C(e_2) \cup C(e_4)| \le |N_B(X)| \le 8$. Since $c(e_2), c(e_4) \ge 5$, $|C(e_2)\cap C(e_4)|\ge 2$. Similarly, $|C(e_1)\cap C(e_3)|\ge 2$. By Lemma 2.7, we may color $e_1$ and $e_3$ with the same color, and color $e_2$ and $e_4$ with the same color. Now the degree sequence for the remaining edges dominates (5, 5, 5, 5, 5). By Hall’s Theorem, there exists a matching covering these edges. So a good coloring of $G'$ can be extended to a good coloring of G, a contradiction.

Next assume that $|S_0|=8$ and $|N_B(S_0)|=7$. Note that, if $\{e_1, e_2, e_3, e_4\} \subset S_0$, then we may again color $e_1$ and $e_3$ with the same color, and color $e_2$ and $e_4$ with the same color; thus extending a good coloring of $G'$ to G, a contradiction. Therefore, $S_0$ contains exactly three edges of $\{e_1, e_2, e_3, e_4\}$. By symmetry, assume that $S_0 = X - e_1$. We may further assume that $|C(e_1) \cap C(e_3)| \le 1$; as otherwise we may repeat the same coloring procedure to obtain a coloring of G. Therefore, $|C(e_1) \cup C(e_3))| \ge 9$, and hence, $C(e_1) - N_B(S_0) \ne \emptyset$. Now we choose a color from $C(e_1) - N_B(S_0)$ to color $e_1$, and a color from $C(e_2) \cap C(e_4)$ to color the edges $e_2$ and $e_4$. Now the degree sequence for the remaining edges dominates (4, 6, 6, 6, 6, 6). By Hall’s Theorem, a good coloring of $G'$ can be extended to a good coloring of G; a contradiction.

This completes the proof for Theorem 1.3.