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?