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.