You are cordially invited to our next Monday Lecture &
Colloquium on May 27th at 14:15 h & 16:00 h at TU Berlin. Location: Technische Universität Berlin Straße des 17. Juni 136 10623 Berlin Time: Monday, May 27th - 14:15 h Lecture: William T. Trotter (Georgia Institute of
Technology) Title: Stability Analysis for Posets Trivially, the
maximum chromatic number of a graph on n vertices is n, and the
only graph which achieves this value is the complete graph K_n.
It is natural to ask whether this result is "stable", i.e., if n
is large, G has n vertices and the chromatic number of G is close
to n, must G be close to being a complete graph? It is easy to
see that for each c>0, if G has n vertices and chromatic
number at least n−c, then it contains a clique whose size is at
least n−2c. We will consider the analogous questions for posets
and dimension. Now the discussion will really become interesting.
Coffee & Tea Break : Room MA 316 - Third Floor [British Reading] Time: Monday, May 27th - 16:00 h s.t. Colloquium: Felix Schröder (Technische Universität Berlin) Title: Lower Bounds on the p-centered coloring number 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. |