Let $G=(V(G), E(G))$ be a graph with maximum degree $\Delta$. For a subset $M$ of $E(G)$, we denote by $G[V(M)]$ the subgraph of $G$ induced by the endvertices of edges in $M$. We call $M$ a semistrong matching if each edge of $M$ is incident with a vertex that is of degree 1 in $G[V(M)]$. Given a positive integer $k$, a semistrong $k$-edge-coloring of $G$ is an edge coloring using at most $k$ colors in which each color class is a semistrong matching of $G$. The semistrong chromatic index of $G$, denoted by $\chi'_{ ss}(G)$, is the minimum integer $k$ such that $G$ has a semistrong $k$-edge-coloring. Recently, Lu\v{ z}ar, Mockov\v{ c}iakov\'a and Sot\'ak conjectured that $\chi'_{ ss}(G)\le \Delta^{ 2}-1$ for any connected graph $G$ except the complete bipartite graph $K_{ \Delta,\Delta}$. In this paper, we settle this conjecture by proving that each such graph $G$ other than a cycle on $7$ vertices has a semistrong edge coloring using at most $\Delta^{ 2}-1$ colors.
Categories: math.CO