Résumé : A b-coloring of a graph is a coloring such that every color class admits a vertex adjacent to at least one vertex receiving each of the colors not assigned to it. The b-chromatic number of a graph G is the maximum number t such that G admits a b-coloring with t colors.Several problems related to b-coloring of graphs have been introduced in the literature. Recently, the theory of b-colorings of graphs has been applied in to some clustering problems in data mining processes. In this talk, we will summarize the last algorithmic and theoretical results obtained on b-coloring and the related notions of b-perfection, b-continuity and b-monotonicity within some graph classes. This is a mix of joint works with C. Betancur, G. Duran, I. Koch, F. Maffray, J. Marenco and M. Valencia-Pabon.
Dernière modification : Wednesday 09 November 2011 | Contact : Cyril.Banderier at lipn.univ-paris13.fr |