I am considering the following heuristic for the graph coloring problem (i.e. to color a graph $G$ using a minimal number of colors so that no two adjacent vertices have the same color):
Explore the vertices of $G$ in the order that they would be explored by a BFS search (with arbitrary starting vertex) and assign each vertex the lowest numbered color not yet used for one of its neighbors.
Since I don't think this algorithm is correct, I am trying to find a counterexample where coloring a graph in this way does not yield a coloring with the minimal number of colors. Does anyone know of such an example?