  A graph $G$ is 3-colorable if and only if it maps homomorphically to the
complete 3-vertex graph $K_3$. The last condition can be checked by a
$k$-consistency algorithm where the parameter $k$ has to be chosen large
enough, dependent on $G$. Let $W(G)$ denote the minimum $k$ sufficient for this
purpose. For a non-3-colorable graph $G$, $W(G)$ is equal to the minimum $k$
such that $G$ can be distinguished from $K_3$ in the $k$-variable
existential-positive first-order logic. We define the dynamic width of the
3-colorability problem as the function $W(n)=\max_G W(G)$, where the maximum is
taken over all non-3-colorable $G$ with $n$ vertices.
  The assumption $\mathrm{NP}\ne\mathrm{P}$ implies that $W(n)$ is unbounded.
Indeed, a lower bound $W(n)=\Omega(\log\log n/\log\log\log n)$ follows
unconditionally from the work of Nesetril and Zhu on bounded treewidth duality.
The Exponential Time Hypothesis implies a much stronger bound
$W(n)=\Omega(n/\log n)$ and indeed we unconditionally prove that
$W(n)=\Omega(n)$. In fact, an even stronger statement is true: A first-order
sentence distinguishing any 3-colorable graph on $n$ vertices from any
non-3-colorable graph on $n$ vertices must have $\Omega(n)$ variables.
  On the other hand, we observe that $W(G)\le 3\,\alpha(G)+1$ and $W(G)\le
n-\alpha(G)+1$ for every non-3-colorable graph $G$ with $n$ vertices, where
$\alpha(G)$ denotes the independence number of $G$. This implies that
$W(n)\le\frac34\,n+1$, improving on the trivial upper bound $W(n)\le n$.
  We also show that $W(G)>\frac1{16}\, g(G)$ for every non-3-colorable graph
$G$, where $g(G)$ denotes the girth of $G$.
  Finally, we consider the function $W(n)$ over planar graphs and prove that
$W(n)=\Theta(\sqrt n)$ in the case.
