Normally, when I think of bread-first search (BFS), I think of it as applying to trees, but vertex coloring is a graph problem, not a tree problem. I suppose you could apply BFS to a graph by adopting the rule that all nodes adjacent to the current one are labeled before moving to a different node.
First, look at a basic example of how simple labeling using lowest-number ordering (called sequential ordering) does not work:
If we label the nodes in clockwise order (A to J) we end up with a 4-coloring, when in fact this graph has a 2-coloring. Now, your rule, prioritizing labeling adjacent nodes will work, because it is a two-coloring. But, there are 3-colorings for which your rule will not work, for example:
In this example we choose A as the root of the "tree", and do its children first, B and C. Then, we choose child B, because it is lower alphabetic order than C, and do all of B's children. We end up with a 4-coloring, when in fact the graph can be 3-colored.