graph coloring using BFS - greedy coloring?

Question

Thinking if I can implement graph coloring using BFS, I came up with the approach pseudo coded below.

Though it does appear like a greedy algorithm, I am not sure of it's correctness. Any expert comments?

colors[MAX_COLORS];
colorsUsedSoFar[] = NIL;
like BFS, color first node u with colors[0] i.e color[u] = colors[0];
colorsUsedSoFar[] += colors[0];

for each node v adjacent to u{
  (if v not already colored){
     color[v] = color from the colorsUsedSoFar[] but NotUsedByItsAdjacents
     If all the colors in colorsUsedSoFar[] are used by adjacents, assign a new color to v)
  }
}

By 'like BFS', I meant using a Queue and processing until Queue exhausts.

Answer 1

This is an example of a greedy coloring algorithm.

The breadth first search (BFS) will implicitly choose an ordering for you.

So the algorithm is correct, but will not always give the optimal coloring (i.e. least number of colours used).

A more common ordering is to order the vertices by their degree, known as the Welsh–Powell algorithm.

Answer 2

If you want your algorithm to color a graph in BFS order then I think your algorithm is perfectly OK in case of correctness except you didn't add nodes into the queue after coloring it inside the for loop. And it's one kind of greedy approach too. You are greedily choosing a node to color which comes first according to levels. Not straightforward greedy but kinda I say.