graph coloring with exactly k colours

Question

Consider a graph G(V,E) with V vertices and E edges. We want to color the vertex graph with exactly K color.

Coloring graph means to assign color to each node in a way which two neighbor vertex shouldn't have same color.

How can we implement this question?

Answer 1

First of all let notice 2 assumption:

1. If |V| < k then it is impossible - so let assume |V| >= k.
2. If we can color the graph with less then k color and |v| > k then it possible also with exactly k color - we can just switch repeating color with one we didn't use it yet.

We can use greedy algorithm to solve this.

Let assign each color with number [1,2,...,k] - let us represent color i by Ci. Start from arbitrary node v1 and assign him C1. Now let run BSF on the graph on for each node choose the minimum color that no exist in his adjustment node - if the other node has no color yet ignore them. If d(v) > k and all his adjustment are in different color then return false.

Pseudo code:

// v.color init as 0 for all V
Queue <- new Queue(v1)
While Queue not empty:
    current <- Queue.pop
    if (current.color != 0 )
         continue
    adjs <- current.getAdj()
    colors = new Set
    for each adjs as adj:
        colors.add(adj.colors)
    for i = 1 to k:
        if i not in colors: //found lowest color avilable
             current.color <- C[i]
             break
    if current.color == 0 return false // cannot assign any color
    Queue.insert(adjs)

Answer 2

The entry on graph coloring algorithms in the wikipedia notes that the question of whether a graph admits a proper (= no two vertices of same color if connected by an edge) coloring with exactly k colors is NP-complete.

The brute-force algorithm is the best you can hope for (unless you have other constraints, such as the graph being bipartite or planar). A brute-force algorithm follows:

#include <iostream>
#include <string>

using namespace std;

// describes a partial answer to the problem
struct Coloring {
    static const int maxV = 5;

    // only the first k colors count
    int colors[maxV];

    void show(int k) const {
        cout << "{";
        for (int i=0; i<k; i++) {
            cout << colors[i] << " ";
        }                                  
        cout << "}" << endl;
    }     
};

// A graph
struct Graph {
    int availableColors;
    int numV;
    bool edges[Coloring::maxV][Coloring::maxV];

    void handleAnswer(Coloring &s) const {
        cout << "EUREKA: ";
        s.show(numV);
    }

    // checks if the k-th vertex avoids being same-color as neighbors
    bool isPartialAnswer(const Coloring &s, int k) const {
        cout << std::string(k, ' ') << "testing: ";
        s.show(k);
        for (int i=0; i<k; i++) {
            for (int j=0; j<i; j++) {
                if ((edges[i][j] || edges[j][i]) 
                    && (s.colors[i] == s.colors[j])) {
                    cout << std::string(k, ' ') << " .. but " 
                        << i << " & " << j << " have same color" << endl;
                    return false;
                }
            }
        }
        return true;
    }

    bool isAnswer(const Coloring &s, int k) const {
        return k == numV;
    }                        
};

void paint(Coloring &s, int k, const Graph &c) {
    // initializes level
    cout << std::string(k, ' ') << "entering k=" << k << ": ";
    s.show(k); 

    // test with each possible color for the next vertex
    for (int i=0; i<c.availableColors; i++) {
        // modify current partial answer
        s.colors[k] = i;
        // is it still a partial answer?
        if (c.isPartialAnswer(s, k+1)) {
            // is it a full answer?
            if (c.isAnswer(s, k+1)) {
                c.handleAnswer(s);
            } else {
                // continue down this road
                paint(s, k+1, c);
            }
        }
    }
    // backtrack: we have exhausted all continuations of this coloring
    cout << std::string(k, ' ') << "closing k=" << k << endl;
}

int main() {
    Graph c = {4, 4, 
        {{0, 1, 0, 0, 0},
        {0, 0, 1, 1, 0},
        {0, 0, 0, 1, 0},
        {0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0},}};

    Coloring s;
    paint(s, 0, c);
    return 0;
}

Disclaimer: this is a canonical example of a backtracking algorithm, and is designed more for clarity than for performance or extensibility.