# Counter example to graph coloring heuristic using BFS

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?

• Which problem are you trying to solve exactly? – Raphael May 26 '15 at 18:36
• actually Petersen graph is a counter example . – kiyarash May 26 '15 at 19:23
• I think that published counter-examples of the four-color theorem, usually predating the proof of the theorem should be counter-examples for you. One from Martin Gardner (1975) is there: mathworld.wolfram.com/Four-ColorTheorem.html. You should find other candidates on this page, and you can easily translate them into graphs. The idea is that if you start with a wrong combination in some part of the graph, you may get blocked, though other choices might work. (to be changed into answer when possible). – babou May 27 '15 at 11:00
• math.stackexchange.com/questions/1299875/… – kiyarash May 27 '15 at 19:32
• What have you tried so far? Have you tried enumerating all graphs of size $\le c$ (for some small constant $c$) to look for a counterexample? We expect you to make a significant effort to solve it on your own before asking and to show us what you've tried. – D.W. May 28 '15 at 6:33

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 ;).

I think that published alleged "counter-examples" of the four-color theorem, usually predating the proof of the theorem should be rewritable as graph counter-examples for you. There is one published (as an April Fool's joke) by Martin Gardner in 1975.

You should find other candidates on this page, and you can easily translate them into graphs. The idea is that if you start with a wrong combination in some part of the graph, you may get blocked, though other choices might work.