Locally irregular graph colourings - distant generalizations

Jakub Przybyło AGH University of Science and Technology

PDF

Minisymposium: VERTEX COLOURINGS AND FORBIDDEN SUBGRAPHS

Content: It is well known that there are no \emph{irregular graphs}, understood as simple graphs with pairwise distinct vertex degrees, except the trivial $1$-vertex case. A graph invariant called the \emph{irregularity strength} was thus introduced aiming at capturing a level of irregularity of a graph. Suppose that given a graph $G = (V,E)$ we wish to construct a multigraph with pairwise distinct vertex degrees of it by multiplying some of its edges. The least $k$ so that we are able to achieve such goal using at most k copies of every edge is denoted by $s(G)$ and referred to as the irregularity strength of $G$. Alternately one may consider (not necessarily proper) edge colourings $c: E\to\{1,2,\ldots,k\}$ with $\sum_{e\ni u}c(e)\neq\sum_{e\ni v}c(e)$ for every pair of distinct vertices $u,v \in V$. Then the least $k$ which permits defining a colouring $c$ with this feature equals $s(G)$. Numerous papers have been devoted to study on this graph invariant since the middle 80's. It also gave rise to many naturally related concepts and the general field of vertex distinguishing graph colourings. The list making up these includes e.g. Zhang's Conjecture, 1--2--3--Conjecture and many others. Within the talk we shall briefly overview main results concerning these as well as their generalizations aiming at distinguishing vertices at a limited distance in a graph. One of the motivations of introducing these is the well known concept of distant chromatic numbers.

Back to all abstracts