Evènement pour le groupe GT Graphes et Applications


Date 2014-11-14  14:00-15:00
TitreLocally irregular graph colourings 
Résumé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 o{1,2,ldots,k}$ with $sum_{e i u}c(e) eqsum_{e i 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. On the other hand, there are many emph{locally irregular graphs}, i.e., those whose only emph{adjacent} vertices are required to have distinct degrees. Analogously as above one might also measure how far a given graph $G=(V,E)$ is from being locally irregular. That is, how large $k$ is needed in order to define an edge colouring $c: E o{1,2,ldots,k}$ with $sum_{e i u}c(e) eqsum_{e i v}c(e)$ for every pair of adjacent vertices $u,v$ of $G$. It is believed that already $k=3$ is sufficient for all graphs containing no isolated edges. This suspicion is commonly referred to as the 1--2--3--Conjecture. 
LieuSalle 178 
OrateurJakub Przyby{l}o 



Aucun document lié à cet événement.

Retour
Retour à l'index