Coloquium by Felix Schröder (Technische Universität Berlin) Lower Bounds on the p-centered coloring number

May 27, 2019 | 04:00 PM s.t.

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.

Time & Location

May 27, 2019 | 04:00 PM s.t.

Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136
10623 Berlin
Room MA 041 (Ground Floor)

Freie Universität Berlin
Technische Universität Berlin
Humboldt-Universität zu Berlin
Deutsche Forschungsgemeinschaft (DFG)