Problem Detail: 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?
Asked By : kiyarash
Answered By : Luke Mathieson
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 ;).
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 ;). Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/42973 Ask a Question Download Related Notes/Documents
