Session 27. Probabilistic and Extremal Combinatorics

Irregularity in graphs

Jakub Przybyło, AGH University of Science and Technology, Poland
How to define an irregular graph? This very basic question was posed and exploited in 1988 as a title of a paper by Chartrand, Erdős and Oellermann. The confusion originates from the well known fact that no antonym of a regular graph, understood as a graph whose all vertices have pairwise distinct degrees, exists, except for the trivial \(1\)-vertex case. This limitation does not concern multigraphs though. Consequently, the following extension of these research was developed as an attempt of designing a graph invariant measuring the level of `irregularity' of a graph. Suppose that given a simple graph \(G=(V,E)\) we are allowed to multiply some of its edges. How small can be the largest necessary multiplicity of an edge so that we are able to construct an irregular multigraph of G, i.e., a multigraph with pairwise distinct vertex degrees? This value was named thei irregularity strength of \(G\), denoted by \(s(G)\). Alternatively, one may consider a (colouring) function \(c:E\to\{1,2,\ldots,k\}\), assigning every edge an integer corresponding to its multiplicity in a desired multigraph. The least \(k\) so that such colouring exists attributing every vertex of \(G\) a distinct sum of incident colours is then equal to \(s(G)\).

This issue was a cornerstone of many other combinatorial questions and colouring problems including e.g. 1-2-3 Conjecture and Zhang's Conjecture, as well as some problems of a more structural flavour, like graph decompositions into locally irregular subgraphs, or complexity problems concerning these.

As appeared this field also constitutes a natural environment for nice applications of the probabilistic method, and provides some observations on random graphs themselves. A few of its consequential results reach far beyond this particular branch of graph theory.

A number of key questions of the field shall be presented during the talk, accompanied by representative results concerning these.

Print version