Strong edge colorings of graphs (Q1126183)

The strong coloring number of a graph \(G\), \(\chi_s'(G)\), is the minimum number of colors for which there is a proper edge-coloring of \(G\) so that no two vertices are incident to edges having the same set of colors. (It is assumed that \(G\) has no isolated edges and at most one isolated vertex.) {Burris} and Schelp [J. Graph Theory, to appear] conjecture that \(\chi_s'(G)\leq n+1\). The present authors show that, for a graph \(G\) of order \(n\), \(\chi_s'(G)\leq\lceil cn\rceil\), where \({1\over 2}<c\leq 1\), if the maximum degree of \(G\) is appropriately bounded as a function of \(n\).