# Attempting to verify the colorability using Wigderson's Algorithm

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.

Consider a star on $$n-4$$ vertices together with a clique on $$4$$ vertices.
• Yes, I see what's the problem is. Would you say that its correct to assume that $G$ is $3$-colorable iff the induced subgraph among all vertices with degree at least $\sqrt{\left| V\right|}$ can be colored as described by Wigderson's algorithm? Oct 13, 2021 at 11:38
• Actually, I can answer my own question: many cliques of size $4$ which are separate to one another. The graph is not $3$-colorable, but the induced subgraph is empty. Oct 13, 2021 at 11:39