3-coloring a graph $G$ is equivalent to partitioning the vertices of $G$ in three independent sets.
The smallest independent set $A$ is at most $n/3$ where $n$ is the order of $G$.
We have $G \setminus A$ is bipartite graph, and the bipartitions can be found in polynomial in $n$ time.
This gives graph coloring and counting of 3 colorings algorithm:
For one coloring: Enumerate independent sets A up to size n/3 If G \ A is bipartite report 3 colorable and stop For counting colorings: set cols:=0 Enumerate independent sets A up to size n/3 If G \ A is bipartite set cols := cols + number_of_2_colorings of G \ A # G \ A might not be connected
Q1 What is the complexity of these algorithms?
Crude upper bound: All subsets (not necessary independent) of size at most $n/3$ experimentally is about $1.883^n$
Q2 What is state of the art of counting 3 colorings?