Counter example to graph coloring heuristic using BFS
Here's one:



The labels indicate the intend BFS ordering (alphabetical). A different ordering can produce a different result, so more work would have to be done to get a graph where your BFS approach fails for every starting point (it would probably be very messy too).

Assuming we follow this ordering however, we get the following colouring:



The key being that $e$ and $f$ get coloured last, so $c$ removes blue from the possibilities, and $d$ removes red, so $e$ and $f$ must have two new colours.

However this graph is 3-colourable:



By choosing to use more colours earlier, it relaxes the constraints later.

I'll also throw in a conjecture that this is smallest counterexample, for no other reason than to challenge others to find smaller ones ;).