A strong edge coloring is an edge coloring of a simple graph in which every color class is an induced matching. Thus edges of the same color neither share a graph vertex nor have endpoints joined by another graph edge (Faudree et al. 1990).
The strong chromatic index is the least number of colors in such a coloring. It equals the chromatic number of the graph
square of the line graph. The Erdős-Nešetril
conjecture predicts an upper bound of , where
is the maximum vertex degree.
The Brualdi-Quinn conjecture bounds the strong chromatic index of a bipartite graph by , where
and
are the maximum vertex
degrees on the two sides (Brualdi and Quinn Massey 1993). Luo et al. (2026)
proved this bound for the fractional chromatic
number of the graph square of the line
graph. Equality is attained by complete
bipartite graphs. For
,
the ordinary strong chromatic index is at most
. The conjectured
exact bound remains open.