Evènement pour le groupe GT Graphes et Applications

Date 2014-09-19  14:00-15:00
TitreAVD coloring 
RésuméAn adjacent vertex-distinguishing edge coloring (AVD coloring) of a graph is a proper edge coloring such that no two neighbors are incident to the same set of colors. Zhang et al. conjectured that every connected graph on at least 6 vertices is AVD (Delta+2)-colorable, where Delta is the maximum degree. In this talk, we prove that (Delta+1) colors are enough when Delta is sufficiently larger than the maximum average degree, denoted mad. We also provide more precise lower bounds for two graph classes: planar graphs, and graphs with mad<3. In the first case, Delta>=12 suffices, which generalizes the result of Edwards on planar bipartite graphs and strengthens the result of Hornak et al. that (Delta+2) is enough. In the second case, Delta>=4 is enough, which is optimal and completes the results of Wang and Wang and of Hocquard and Montassier.  
LieuSalle 178 
OrateurHervé Hocquard 

Aucun document lié à cet événement.

Retour à l'index