Improved bounds for centered colorings
Time: 10:30 -- Location: Salle Henri Poincaré du LIX
A vertex coloring \phi of G is p-centered for each connected subgraph H of G either \phi uses more than p colors on H or 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 gr aphs 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