#149: the degree-4 strong clique number is 20
The target (erdosproblems.com/149, OPEN). A strong edge coloring assigns different colors to every two edges at distance at most two. Equivalently, it colors L(G)2. The Erdős-Nešetřil conjecture predicts the optimal general bound; even its maximum-degree-4 case remains unresolved.
An exact clique result. Write
Omega4 = max omega(L(G)2)
over simple G with Delta(G)≤4.
A July 2026 preprint of Kumar, Mohar, and Pragada proves the general bound
omega(L(G)2) ≤ (2607/1987) Delta(G)2.
At Delta=4 the right side is 41712/1987=21-15/1987. Clique number is an integer, so Omega4≤20.
The independent two-vertex blowup of C5 gives equality. It is 4-regular with 20 edges, and every two edges have line-graph distance at most two. Thus L(G)2=K20, and
Omega4=20.
A disclosed source repair. The preprint is currently v1 and contains a genuine typo: an auxiliary minimum is taken over [0,1/4] immediately after the proof shows that no value in that interval works. The audit does not silently ignore this. It reruns the induction with the fixed constant beta=620/1987. Exact rational expansion verifies the paper's sum-of-a-square certificate, a negative discriminant for its remaining quadratic, and the final induction identity. No later step uses minimality of the malformed auxiliary quantity. The passage from the repaired bipartite lemma to the general coefficient uses Faron and Postle's published theorem with matching quantifiers.
What remains open. A strong clique gives a lower bound on the number of colors, not an upper bound. The blowup forces 20 colors, while Huang, Santana, and Yu proved that 21 always suffice at maximum degree 4. Therefore the exact coloring statement is still only
20 ≤ X4 ≤ 21.
This is a literature-derived partial, not our discovery and not a solution of Problem 149. The live page showed no claimed proof or current worker on 11 August 2026 and still quoted the older 4/3 strong-clique coefficient. The site had already used the same preprint in Problem 934, but only for its separate Section 3 L(G)3 degree-diameter construction; that source overlap is explicitly disclosed.