A p-centered coloring is a vertex-coloring of a graph G such that every connected subgraph H of G either receives more than p colors or there is a color that appears exactly once in H. The concept was introduced by Nešetřil and Ossona de Mendez as a local condition for measuring sparsity.
We prove lower bounds on the p-centered coloring numbers. For outerplanar graphs, we show that their maximum p-centered coloring number is in Theta(p log p). We have examples of graphs of treewidth k needing (p+k choose k) colors, this matches the upper bound of Pilipczuk and Siebertz.
We show that planar graphs may require Omega(p^2 log(p)) colors, while all of them admit a p-centered coloring with O(p^3 log(p)) colors. This improves an O(p^19) bound by Pilipczuk and Siebertz.
May 27, 2019 | 04:00 PM s.t.
Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136
Room MA 041 (Ground Floor)