  For $p\in \mathbb{N}$, a coloring $\lambda$ of the vertices of a graph $G$ is
{\em{$p$-centered}} if for every connected subgraph~$H$ of $G$, either $H$
receives more than $p$ colors under $\lambda$ or there is a color that appears
exactly once in $H$. In this paper, we prove that every $K_t$-minor-free graph
admits a $p$-centered coloring with $\mathcal{O}(p^{g(t)})$ colors for some
function $g$. In the special case that the graph is embeddable in a fixed
surface $\Sigma$ we show that it admits a $p$-centered coloring with
$\mathcal{O}(p^{19})$ colors, with the degree of the polynomial independent of
the genus of $\Sigma$. This provides the first polynomial upper bounds on the
number of colors needed in $p$-centered colorings of graphs drawn from proper
minor-closed classes, which answers an open problem posed by Dvo\v{r}{\'a}k.
  As an algorithmic application, we use our main result to prove that if
$\mathcal{C}$ is a fixed proper minor-closed class of graphs, then given graphs
$H$ and $G$, on $p$ and $n$ vertices, respectively, where $G\in \mathcal{C}$,
it can be decided whether $H$ is a subgraph of $G$ in time
$2^{\mathcal{O}(p\log p)}\cdot n^{\mathcal{O}(1)}$ and space
$n^{\mathcal{O}(1)}$.
