# Complexity of graph 3 coloring and counting algorithm

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?

• Your second algorithm is double-counting colorings in which two sets have size $\le n/3$. Dec 4, 2019 at 19:47
• @SamZbarsky Thanks, you are right. Can we modify the algorithm to keep track of colorings where two color classes are < n/3?
– joro
Dec 5, 2019 at 9:30
• Such an algorithm may be incorrect, as any 3-coloring of $C_5$ has color classes of size 1,2,2, and n=5. Dec 5, 2019 at 9:34
• @LeechLattice I don't think $C_5$ is problem. Problem appear to be $K_3 \cup K_1$ with sizes 1,1,2 and n=4
– joro
Dec 5, 2019 at 15:06

For finding colorings, let $$A=K_4 \cup \bar{K^m}$$, which is a $$K_4$$ and $$m$$ disjoint vertices. The algorithm keeps enumerating independent sets without success, as $$A$$ is not 3-colorable.
Both have complexity of the order $$1.883^n c$$ where $$c$$ is some constant.