Pour la reprise du séminaire nous aurons le plaisir d’écouter Stefan Felsner (TU Berlin) nous parler de “Improved bounds for centered colorings”. Veuillez noter que l’exposé sera 30mn plus tôt que l’horaire habituel (toujours en salle Philippe Flajolet au LIX). Le résumé est disponible ci-dessous.

Le programme du séminaire est disponible ici : https://galac.lri.fr/pages/combi-seminar.html

Résumé: A vertex coloring ϕ of G is p-centered if for each connected subgraph H of G either ϕ uses more than p colors on H or there is a color that appears exactly once on H. Centered colorings form one of the families of parameters that allow to capture notions of sparsity of graphs: A class of graphs has bounded expansion if and only if there is a function f such that for every p > 1, every graph in the class admits a p-centered coloring using at most f(p) colors. In this paper, we give upper and lower bounds for the maximum number of colors needed in a p-centered coloring of graphs from several widely studied graph classes. This includes outerplanar graphs, planar graphs, graphs of bounded treewidth and graphs of bounded degree. Joint work with M. Debski, P. Micek, and F. Schroeder