The chromatic polynomial of graph $P(G,x)$ is univariate polynomial which counts the number of colorings of $G$ with $x$ colors for natural $x$.
Graph is not $k$ colorable iff $P(G,k)=0$.
The chromatic polynomial of clique $K_n$ is $x(x-1)(x-2)\ldots(x-(n-1))$
A graph is 3-colorable iff $P(G,x) \not \equiv 0 \pmod{x-3}$ (in other words 3 is not a root of $P(G,x)$.
The goal is to check 3-colorability by computing $P(G,x) \pmod{x-3}$.
For non adjacent vertices $u$ and $v$, $G+uv$ is the graph with the edge $uv$ added and the graph $G/uv$ is obtained by merging the two vertices.
According to wikipedia
$$P(G,k)= P(G+uv, k) + P(G/uv,k) \qquad (1) $$
And the terminating conditions are cliques.
So $G$ is not 3-colorable iff all terminal cliques are on more than $3$ vertices.
When computing (1) $\mod x-3$, we have the following terminal conditions.
(A) if $F$ contains $K_4$ as (induced) subgraph it is not 3-colorable and we return $P(F,k) \equiv 0 \pmod{x-3}$ without bothering to compute later.
(B) if $F$ is clique on 3 or less vertices, $G$ is 3-colorable since this a terminating clique.
Adding edges and merging vertices tends to induce $K_4$ and (A) is often hit, which makes computing $P(G,x) \pmod{x-3}$ strictly faster than the full $P(G,x)$ and this decides 3-colorability.
Consider the following naive algorithm for checking 3-colorability using $P(G,x) \pmod{x-3}$.
function color3(G: connected graph)
#returns 0 if G is not 3-colorable, otherwise reports it is and stops
if G contains induced K_4
return 0
if G is a clique on 3 or less vertices
report '3-colorable'. Stop.
if we can add edge uv which induces K_4 in G
return color3(G/uv) #the induced K_4 contributes 0 to the sum
#the above makes the problem strictly smaller
#this might be greatly improved by trying to induce K_4-e
[C] pick the lexicographic first non-adjacent u,v and return color3(G+uv)+color3(G/uv)
One call to color3 is polynomial, so the complexity depends on the number of double recursion in [C].
According to Wikipedia the worst case for computing (1) is $\phi^{n+m}$. 3-coloring 4-regular graphs is NP-complete, so for 4-regular it is $\phi^{3n}$.
Appears to me terminating by induced $K_4$ would greatly improve the running time.
Questions:
Q1 What is the complexity of color3?
$O(c^n)$ for small $c$ will be of practical interest. $2^{o(n)}$ might indicate complexity collapse.
Q2 How to improve [C]?
There might be other improvements like other 4-chromatic subgraph or $F$ being in a graph class where coloring is polynomial.
Experimental results:
For several 4-regular graphs on 246 vertices which are the line graphs of 3-regular graphs color3 found 3-coloring in less than a minute in sage 6.2 implementation. For several smaller graphs which are not 3-colorable it correctly returned 0. For reduction SAT to 3-color the running time was fast too.
Added Choosing the lexicographically first edge appears good choice. It adds high degree vertices and is experimentally much faster than choosing a random edge. (Another good choice is too add edge between the two highest degree vertices).
Q3 How to explain the fast experimental results, including 4-chromatic graph on 75 vertices and the reductions from SAT?
Sage implementation: https://gist.github.com/jor0/039127ab69dd8934c105
Q4 For 4-regular graph on 50 vertices, what is the current record for maximum number of steps of the above implementation?
