Evènement pour le groupe GT Graphes et Applications

Date 2014-06-06  14:00-15:00
Titre2-distance coloring of not-so-sparse graphs 
RésuméThe 2-distance coloring of a graph G is a proper coloring of G where every pair of vertices sharing a common neighbor receives different colors. The "maximum average degree" or "mad" of a graph is the maximum among the average degrees of its subgraphs. This is a way to evaluate the density (or the sparseness) of a graph, both globally and locally. Several results exist about the lesser number of colors needed for 2-distance coloring of graphs with bounded mad. However, in all these results, the bound is strictly less than 4. We present upper and lower bounds for the "2-distance chromatic number" of graphs with mad bounded by 2k for every k.  
LieuSalle 178 
OrateurClément Charpentier 

Aucun document lié à cet événement.

Retour à l'index