Séminaire d'équipe(s) Graphs, ALgorithms and Combinatorics
2-distance coloring of not-so-sparse graphs.
Clement Charpentier
16 May 2014, 14:30 - 16 May 2014, 15:30 Salle/Bat : 465/PCRI-N
Contact :
Activités de recherche :
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 lesser than 4.
We present upper and lower bounds for the "2-distance chromatic number" of graphs with mad bounded by 2k for every k.
