The algorithm of Wigderson (see here) can color a graph that is known to be $3$-colorable in $O\left( \sqrt{\left| V \right|} \right)$ colors. This is done in $O\left( |V| + |E|\right)$ time.
For those who are not familiar with the algorithm, I'll give a brief description of it (it can be used for any $k$-colorable graph, but lets assume $k=3$).
We loop on $V$ until a $v\in V$ is found such that $\deg v \geq \sqrt {|V|}$. If no such $v\in V$ exists, then the graph has a bounded degree of $\sqrt{|V|}$, and can be easily colored using $\sqrt{|V|}$ colors in linear time (by simply iterating over all vertices and selecting an unoccupied color among the ones of its neighbours).
Once such a $v\in V$ is found, we denote by $G_v$ the induced subgraph of $v$'s neighbours. As $G$ is $3$-colorable, $G_v$ is $2$-colorable. That means, $G_v$ can be colored using $2$ colors in linear time, by a simple "red"-"blue" algorithm. By selecting a third color, $v$ can be colored as well. Once we move to the next $v\in V$, we use a different color class (each color class contains $3$ colors).
We know that $\left|V_{G_v}\right| \geq \sqrt{|V|}$. Meaning, this procedure occurs for at most $\frac{\left| V\right|}{\sqrt{\left| V\right|}} = \left| V \right|$ iterations. The running time is linear each time, meaning the entire running time is still linear (in the original $G$).
So far is the algorithm. I would like to use in the following way:
Given a graph $G=(V,E)$, try coloring it using Wigderson's algorithm. If the graph is actually $3$-colorable, this will succeed. You will receive a $O\left( \sqrt{\left| V \right|}\right)$-coloring. If $G$ is not $3$-colorable, I believe this will fail because there should be at least one vertex $v \in V$ whose color, under any coloring function, cannot be among $\left\{ 0,1,2 \right\}$ (up to a permutation of the colors...). Meaning, under any coloring, its neighbours use all the colors $\left\{ 0,1,2 \right\}$ and the induced subgraph of its neighbours is not $2$-colorable. This means that when we try to $2$-color it by a simple "red"-"blue" algorithm, we will fail. So by checking whether or not we fail in Wigderson's Algorithm, can we not verify in reality whether $G=(V,E)$ is $3$-colorable or not?
I assume the answer is no, yet I'm looking for my mistake, and if possible, to elaborate on where exactly I am wrong in here.
