A bound on the strong chromatic index of a graph (Q1354718)

The strong chromatic index \(s\chi'(G)\) of a graph \(G\) is the minimum number of colors in a proper edge coloring of a graph in which no edge is adjacent to an edge of the same color. It is proved that \(s\chi'(G)\leq 1.998\Delta^2\), where \(\Delta\) is the maximum degree of a vertex of \(G\). This answers a question of Erdös and Nešetřil, which was to show that there exists an \(\varepsilon>0\) such that \(s\chi'(G)\leq(2- \varepsilon)\Delta^2\). It is conjectured that, in fact, \(s\chi'(G)\leq{5\over 4}\Delta^2\), with the extremal example being the graph obtained from a \(C_5\) by replacing each vertex with a large independent set and each edge by the appropriate complete bipartite graph.