The Erdős-Nešetril conjecture asserts that every simple graph of maximum vertex degree 
has a strong edge coloring
with at most 
colors (Faudree et al. 1990). A strong
edge coloring partitions the edges into induced
matchings, so two edges of the same color neither
share a graph vertex nor have adjacent endpoints.
The coefficient 
cannot be reduced. Replace each graph
vertex of a 5-cycle graph by an independent set of 
vertices and each graph
edge by all edges between the corresponding sets. The resulting graph has maximum
vertex degree 
and 
edges, all of which must
receive different colors in a strong edge coloring.
The conjecture remains open (Bloom 2026).
This is problem 149 in the Erdős problems collection (Bloom 2026).
