The Strong Chromatic Index of Graphs with Restricted Ore-Degrees

Abstract

A strong edge-coloring is a proper edge-coloring such that two edges with the same color are not allowed to lie on a path of length three. The strong chromatic index of a graph $G$, denoted by $s^{\prime }(G)$, is the minimum number of colors in a strong edge-coloring. We denote the degree of a vertex $v$ by $d(v)$. Let the $Ore-degree$ of a graph $G$ be the maximum value of $d(u)+d(v)$, where $u$ and $v$ are adjacent vertices in $G$. Let $F_3$ denote the graph obtained from a $5$-cycle by adding a new vertex and joining it to a pair of nonadjacent vertices of the $5$-cycle. In $2008$, Wu and Lin [J. Wu and W. Lin, The strong chromatic index
of a class of graphs, Discrete Math., $308(2008),6254-6261]$ studied the strong chromatic index with respect to the Ore-degree. Their main result states that if a connected graph $G$ is not $F_3$ and its Ore-degree is $5$, then $s^{\prime }(G)\le 6$. Inspired by the result of Wu and Lin, we investigate the strong edge-coloring of graphs with Ore-degree 6. We show that each graph $G$ with Ore-degree $6$ has $s^{\prime }(G)\le 10$. With the further condition that $G$ is bipartite, we have $s^{\prime }(G)\le 9$. Our results give general forms of previous results about strong chromatic indices of graphs with maximum degree $3$.