Evènement pour le groupe GT Graphes et Applications

Date 2010-10-15  14:00-15:00
TitreVertex distinguishing labelings of graphs 
RésuméLet G be a simple connected graph of order n ≥ 3, and let us label each edge of G with a positive integer. As a result we obtain a vertex colouring, where the colour of a vertex is defined by the sum of the numbers on its incident edges. Suppose we use only integers 1,2,...,k as labels. How large must k be for a given graph G ? A striking conjecture of Karonski,Luczak and Thomason asserts that the numbers 1, 2, 3 are sufficient for every graph. We shall discuss best known results in pursuit of the proof of this conjecture, as well as a number of related problems. Among others, we will focus on the “total” counterpart of this conjecture (where also vertices obtain their own initial labels), and the problem where all the vertices, not only the neighbouring ones, are required to have distinct colours (i.e., sums). The later introduces a well known graph invariant called irregularity strength of a graph.  
LieuSalle 178 
OrateurJakub Przybylo 

Aucun document lié à cet événement.

Retour à l'index