0
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Which problem are you trying to solve exactly? $\endgroup$
    – Raphael ♦
    May 26, 2015 at 18:36
  • $\begingroup$ actually Petersen graph is a counter example . $\endgroup$
    – KFkf
    May 26, 2015 at 19:23
  • 1
    $\begingroup$ 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). $\endgroup$
    – babou
    May 27, 2015 at 11:00
  • 1
    $\begingroup$ math.stackexchange.com/questions/1299875/… $\endgroup$
    – KFkf
    May 27, 2015 at 19:32
  • $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    May 28, 2015 at 6:33

2 Answers 2

Reset to default
1
$\begingroup$

Here's one:

A graph.

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 graph, coloured using the BFS approach.

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:

The graph, coloured using 3 colours.

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

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.