Evènement pour le groupe GT Graphes et Applications

Date 2013-04-05  14:00-15:00
TitreFrom edge-colouring to strong edge-colouring 
RésuméThe strong edge-colouring of G is a proper edge-colouring of G such that two edges joined by another edge are coloured with distinct colours. In other words a strong edge-colouring of a graph is a partitioning of its edge set in a set of induced matchings. First we will present several results about strong edge-colouring. In the second part we discuss a natural generalization of both edge- and strong edge-colouring: the k-intersection edge-colouring. It is a proper edge-colouring such that every pair of adjacent vertices u,v share at most k colours. Contrary to the previous two notions, colouring even "simple" classes of graphs does not seem to be an easy task. We will present asymptotically tight upper and lower bounds for the k-intersection chromatic index for these families of graphs. Moreover we show that, not surprisingly, the associated decision problem is NP-complete for different values of k. This is a joint work with different sets of authors from Bordeaux, Montpellier, Orsay, India, Japan and Taiwan.  
LieuSalle 178 
OrateurPetru Valicov 

Aucun document lié à cet événement.

Retour à l'index