Experiments in graph 3-coloring

3-coloring using independent sets

• By definition, vertices in an independent set (IS) share no edges. So these vertices can all be colored with one color.
• If after the removal of these vertices (and incident edges), the graph is 2-colorable, then we have a valid 3-coloring.

Fig 1: An independent set (red vertices)

Fig 2: Graph without independent set

Fig 3: Graph without independent set is 2-colorable

Fig 4: Fully colored graph with 3 colors

Interesting points about this approach

• Not all independent sets work, since G - IS may not be 2-colorable.
• Enumerating all independent sets is equivalent to enumerating the power set of the vertices and determining if they form an independent set. This has 2^v iterations, each taking about v^2 time. This is asymptotically better than 3^v iterations required for a brute force 3-coloring.
• If a graph is 3-colorable, then we can always find one color in a valid 3-coloring that is applied to at most floor(v/3) vertices. This implies that when enumerating all independent sets, we need to only find independent sets of size floor(v/3) or less. This is still O(2^n), by the way.

Optimization for this approach

• We start with brute force enumeration, as below, where 1 implies inclusion of the vertex and 0 its exclusion from the independent set.
• {1, 0, 0, ..., 0} - start by choosing v0
• {1, 1, 0, ...., 0} - after we choose v0 and v1 in the independent set.
• {1, 0, 1, ...., 0} - if we decide that v0 and v1 cannot be in an independent set (because they share an edge) and move on to v0 and v2.
• In general, if current selection is an independent set, keep the latest added vertex and include the next available vertex.
• In general, if current selection is not an independent set (because the latest vertex has one or more edges with previous vertices in the independent set), drop the latest added vertex and choose the next available one.

3-coloring with brute force

• This is exhaustive, brute force approach. We try each combination, till we find a valid coloring.
• Let the colors be 0, 1 and 2. Each color combination is an n-tuple. E.g. {0, 2, 1, 0, 0, 1, 1, 2, ...}. This colors vertex v0 with color 0, v1 with color 2, v2 with color 1 and so on.
• This is O(3^n), but seems to run faster in practice. Perhaps it has a tighter bound than O(3^n).

Optimization for this approach

• We order vertices arbitrarily as v0, v1, v2, ..., vn.
• We enumerate current color selection lexicographically. E.g.
1. 0
2. 0, 0, if the previous selection is a valid coloring
3. 0, 0, 0 if the previous selection is a valid coloring
4. 0, 0, 1 if the previous selection is not a valid coloring
5. 0, 0, 2 if the previous selection is not a valid coloring
6. 0, 1 if the previous selection is not a valid coloring
7. 0, 1, 0 if the previous selection is a valid coloring
8. and so on.

3-coloring greedily

• This is a simple approach, very fast in practice, but cannot color all colorable graphs.
• Order vertices by descending order of degree.
• Greedily choose the lowest color that is valid.
• Repeat above step till all vertices are colored.
• Runs in O(v^2) time.