Improved bounds for centered colorings

摘要: A vertex coloring $\phi$ of a graph $G$ is $p$-centered if for every connected subgraph $H$ either uses more than $p$ colors on or there color that appears exactly once $H$. Centered colorings form one the families parameters allow to capture notions sparsity graphs: class graphs has bounded expansion and only function $f$ such $p\geq1$, in admits using at most $f(p)$ colors. In this paper, we give upper bounds maximum number needed from several widely studied classes. We show that: (1) planar admit with $\mathcal{O}(p^3\log p)$ where previous bound was $\mathcal{O}(p^{19})$; (2) degree $\mathcal{O}(p)$ while it conjectured they may require exponential $p$; (3) avoiding fixed as topological minor polynomial All these imply algorithms computing colorings. Prior work were no non-trivial lower known. (4) are treewidth $t$ $\binom{p+t}{t}$ any matches bound; (5) $\Omega(p^2\log coloring.