Actualités
  Période
semaine
ou mois
aucune période


  Thèmes:
Thèses
Colloques
Autres
Groupes
Tous les thèmes

   
  Liens:
Voir les thèses

Voir les colloques

Voir les autres événements

Voir la page des groupes

Accéder à l'intranet

Intitulé:   
From edge-colouring to strong edge-colouring
du 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
Retour à l'index