Title: On degree irregularities in graphs

Abstract: The irregularity strength of a graph \(G\), \(s(G)\), is the least \(k\) admitting a \(\{1,2,\ldots,k\}\)-weighting of the edges of \(G\) assuring distinct weighted degrees of all vertices, or equivalently the least possible maximal edge multiplicity in an irregular multigraph obtained of \(G\) via multiplying some of its edges. The most well-known open problem concerning this graph invariant is the conjecture posed in 1987 by Faudree and Lehel that there exists a constant \(C\) such that \(s(G)\leq \frac{n}{d}+C\) for each \(d\)-regular graph \(G\) with \(n\) vertices and \(d\geq 2\) (while a straightforward counting argument yields \(s(G)\geq \frac{n+d-1}{d}\)). We shall discuss recent results drawing us near solving this conjecture, e.g. from [3,4], as well as a few related problems, such as the concept of irregular subgraphs introduced recently by Alon and Wei [1,2]. References:

1. [1] N. Alon, F. Wei, Irregular Subgraphs, arXiv:2108.02685.
2. [2] J. Fox, S. Luo, H.T. Pham, On random irregular subgraphs, arXiv:2207.13651.
3. [3] J. Przybylo, Asymptotic confirmation of the Faudree-Lehel Conjecture on irregularity strength for all but extreme degrees, J. Graph Theory 100 (2022) 189–204.
4. [4] J. Przybylo, F. Wei, On the asymptotic confirmation of the Faudree-Lehel Conjecture for general graphs, arXiv:2109.04317.

Jakub Przybyło spent his entire scientific life with AGH University of Science and Technology in Kraków. Now he works there as an associate professor in the Department of Applied Mathematics He is the author of many articles on graph theory published in renowned journals. In 2017, he obtained the title of habilitated doctor by presenting a dissertation entitled 'Locally and globally irregular coloring of graphs'. He is also a valued academic teacher with huge academic experience.