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'(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'(G) \leq 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'(G) \leq 10\). With the further condition that \(G\) is bipartite, we have \(s'(G) \leq 9\). Our results give general forms of previous results about strong chromatic indices of graphs with maximum degree \(3\).