Skip to content

Erdős Problem #149

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: graph theory.

Read this status correctly

The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.

The question in plain language

A strong edge colouring assigns colours to the edges of a graph so that any two edges of the same colour form an induced matching: they share no endpoint, and no edge of the original graph joins an endpoint of one to an endpoint of the other. The minimum number of colours is the strong chromatic index, here \(s(G)\).

Erdős and Nešetřil conjectured that for a graph with maximum degree \(\Delta\),

\[ s(G)\le\frac54\Delta^2. \]

Equivalently, it asks for a vertex-colouring bound for the square of the line graph \(L(G)^2\). The ordinary edge chromatic number, which forbids only sharing endpoints, is a different quantity.

A small example

For a five-cycle \(C_5\), \(\Delta=2\). Any two different edges are either adjacent or have endpoints joined by another cycle edge, so no two can share a colour in a strong edge colouring. Consequently \(s(C_5)=5\), attaining \((5/4)\cdot 2^2=5\). This is the sharp lower example at degree two.

Blowing up the vertices of a five-cycle gives examples explaining the constant \(5/4\) for even larger degree, but does not prove the upper bound for all graphs. An arbitrary proper edge colouring may use too few colours because nonadjacent edges can still conflict at distance two.

What is known

The general conjecture remains OPEN. Hurley, de Joannis de Verclos and Kang, An improved procedure for colouring graphs of bounded local density, prove the asymptotic bound

\[ s(G)\le1.772\Delta^2 \]

for sufficiently large \(\Delta\). Earlier results of Molloy–Reed, Bruhn–Joos and Bonamy–Perrett–Postle improved a sequence of weaker constants. Neither a \(1.772\) constant nor the exact \(\Delta\le3\) results prove the conjectured \(1.25\).

At small degree, \(s(G)\le5\) when \(\Delta\le2\), and the optimal general bounds \(s(G)\le10\) for \(\Delta=3\) and \(s(G)\le21\) for \(\Delta=4\) are source-attributed results. The separate conjecture on the clique number of \(L(G)^2\) is also not known in full; a clique bound cannot alone bound the chromatic number.

GCL's current state

The pinned and maintained Erdős #149, edited April 2026, classify it OPEN. The original issue is #1418. The \(1.772\) theorem was checked against the primary research abstract and SODA publication record; its full probabilistic colouring procedure was not independently recreated.

The original issue contains an authenticated RESULT/1 source report. This is unadjudicated source evidence only, not independent mathematical certification or editorial admission.

What remains

A bounded fixture enumerates small graphs and builds \(L(G)^2\) directly. Check that a colouring of its vertices is equivalent to a partition of the original edges into induced matchings. Acceptance: \(C_5\) requires exactly five strong colours, while a path on four vertices needs three. Use exhaustive graph and colour enumerations only for small inputs, with no claim of proving the universal quadratic constant.

Sources and claim boundaries

No proof of the proposed \(5/4\) bound, independent algorithm certification or editorial admission is claimed.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1418 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: STATEMENT_CAPTURE_REQUIRED.
  • Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
  • External mathematical status: consult current problem page and its dated bibliography.

Back to catalogue · Compendium introduction