Improved bounds for centered colorings

Abstract

A vertex coloring $\varphi$ of a graph $G$ is $p$-centered if for every connected subgraph $H$ of $G$ either $\varphi$ uses more than $p$ colors on $H$ 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 graphs has bounded expansion if and only if there is a function $f$ such that for every $p\ge 1$, every graph in the class admits a $p$-centered coloring using at most $f(p)$ colors. In this paper, we give upper bounds for the maximum number of colors needed in a $p$-centered coloring of graphs from several widely studied graph classes. We show that: (1) planar graphs admit $p$-centered colorings with $\mathcal{O}(p^3\log p)$ colors where the previous bound was $\mathcal{O}(p^{19})$; (2) bounded degree graphs admit $p$-centered colorings with $\mathcal{O}(p)$ colors while it was conjectured that they may require exponential number of colors in $p$; (3) graphs avoiding a fixed graph as a topological minor admit $p$-centered colorings with a polynomial in $p$ number of colors. All these upper bounds imply polynomial algorithms for computing the colorings. Prior to this work there were no non-trivial lower bounds known. We show that: (4) there are graphs of treewidth $t$ that require $\left(\genfrac{}{}{0ex}{}{p+t}{t}\right)$ colors in any $p$-centered coloring and this bound matches the upper bound; (5) there are planar graphs that require $\Omega (p^2\log p)$ colors in any $p$-centered coloring.

References in corpus (2)

• A note on planar partial 3-trees
• Improved bounds for weak coloring numbers

Cited by in corpus (8)

• Improved product structure for graphs on surfaces
• Improved bounds for weak coloring numbers
• Separating layered treewidth and row treewidth
• Product structure of graphs with an excluded minor
• A general framework for hypergraph colouring
• Two lower bounds for $p$-centered colorings
• Universality in minor-closed graph classes
• The grid-minor theorem revisited