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.


1 Answer 1


Consider a star on $n-4$ vertices together with a clique on $4$ vertices.

  • $\begingroup$ 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? $\endgroup$ Commented Oct 13, 2021 at 11:38
  • 2
    $\begingroup$ 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. $\endgroup$ Commented Oct 13, 2021 at 11:39
  • $\begingroup$ Any assumption which leads to a polynomial time algorithm for 3-coloring is likely false. $\endgroup$ Commented Oct 13, 2021 at 11:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.