On asymptotic confirmation of the Faudree-Lehel Conjecture on the irregularity strength of graphs
We call a multigraph irregular if it has pairwise distinct vertex degrees. No nontrivial (simple) graph is thus irregular. The irregularity strength of a graph $G$, $s(G)$, is a specific measure of the ``level of irregularity'' of $G$. It might be defined as the least $k$ such that one may obtain an irregular multigraph of $G$ by multiplying any selected edges of $G$, each into at most $k$ its copies. In other words, $s(G)$ is the least $k$ admitting a $\{1,2,\ldots,k\}$-weighting of the edges of $G$ assuring distinct weighted degrees for all the vertices, where the weighted degree of a vertex is the sum of its incident weights. The most well-known open problem concerning this graph invariant is the conjecture posed in 1987 by Faudree and Lehel that there exists an absolute constant $C$ such that $s(G)\leq \frac{n}{d}+C$ for each $d$-regular graph $G$ with $n$ vertices and $d\geq 2$, whereas a straightforward counting argument implies that $s(G)\geq \frac{n}{d}+\frac{d-1}{d}$. Until very recently this conjecture had remained widely open. We shall discuss recent results confirming it asymptotically, up to a lower order term. If time permits we shall also mention a few related problems, such as the 1--2--3 Conjecture or the concept of irregular subgraphs, introduced recently by Alon and Wei, and progress in research concerning these.
