Two lower bounds for p-centered colorings
share
Given a graph G and an integer p, a coloring f : V(G) →ℕ is p-centered if for every connected subgraph H of G, either f uses more than p colors on H or there is a color that appears exactly once in H. The notion of p-centered colorings plays a central role in the theory of sparse graphs. In this note we show two lower bounds on the number of colors required in a p-centered coloring. First, we consider monotone classes of graphs whose shallow minors have average degree bounded polynomially in the radius, or equivalently (by a result of Dvořák and Norin), admitting strongly sublinear separators. We construct such a class such that p-centered colorings require a number of colors exponential in p. This is in contrast with a recent result of Pilipczuk and Siebertz, who established a polynomial upper bound in the special case of graphs excluding a fixed minor. Second, we consider graphs of maximum degree Δ. Dębski, Felsner, Micek, and Schröder recently proved that these graphs have p-centered colorings with O(Δ^2-1/p p) colors. We show that there are graphs of maximum degree Δ that require Ω(Δ^2-1/p p ln^-1/pΔ) colors in any p-centered coloring, thus matching their upper bound up to a logarithmic factor.
READ FULL TEXT