On the dynamic width of the 3-colorability problem

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} emathrm{P}$ implies that $W(n)$ is unbounded. Indeed, a lower bound $W(n)=Omega(loglog n/logloglog 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)lefrac34,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.