Faudree–Lehel's irregularity-strength conjecture

Let GG be a dd-regular graph on nn vertices with d>1d>1. An irregular edge weighting assigns real weights to the edges so that all vertices have distinct weighted degrees, and s(G)s(G) is the least kk for which an irregular weighting using weights from {1,2,,k}\{1,2,\ldots,k\} exists. Faudree–Lehel's irregularity-strength conjecture. There is a constant C>0C>0 such that, for every such graph,

s(G)nd+C.s(G)\leq\frac{n}{d}+C.

The source says that this conjecture remains open, although its asymptotic validity has been confirmed. It is a central conjecture concerning irregularity strength.

Sources & referencesView supporting material

Primary source

Kecai Deng and Hongyuan Qiu, “Every graph is uniform-span (2,2)-choosable: Beyond the 1-2 conjecture”, arXiv:2506.14253 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.