5
$\begingroup$

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?

$\endgroup$
4
  • 1
    $\begingroup$ Your second algorithm is double-counting colorings in which two sets have size $\le n/3$. $\endgroup$ Dec 4, 2019 at 19:47
  • $\begingroup$ @SamZbarsky Thanks, you are right. Can we modify the algorithm to keep track of colorings where two color classes are < n/3? $\endgroup$
    – joro
    Dec 5, 2019 at 9:30
  • $\begingroup$ Such an algorithm may be incorrect, as any 3-coloring of $C_5$ has color classes of size 1,2,2, and n=5. $\endgroup$ Dec 5, 2019 at 9:34
  • $\begingroup$ @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 $\endgroup$
    – joro
    Dec 5, 2019 at 15:06

1 Answer 1

2
$\begingroup$

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.

For counting colorings, the complement of a complete graph takes the longest time.

Both have complexity of the order $1.883^n c$ where $c$ is some constant.

$\endgroup$
1
  • $\begingroup$ Thanks. As per comment in the question, the counting algorithm doubly counts when two color classes are of size < n/3. Can we modify the algorithm to count correctly? $\endgroup$
    – joro
    Dec 5, 2019 at 9:32

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.