-2
$\begingroup$

I found this question on the net and I'm wondering what is the process for answering such questions? I assume there is some formula that works for all graphs?

1.a. Consider the undirected graph with vertices $A$, $B$, $C$, $D$, $E$, $F$ and edges $AB$, $AC$, $BD$, $CE$, $DF$ and $EF$ (i.e., the graph is the 6-cyle $ABDFECA$). What is the minimal number of colours needed to colour this graph?

1.b. Show how when considering the ordering $A$, $B$, $C$, $D$, $E$, $F$ of the vertices in the above graph, a greedy algorithm will find this minimal number, and find one other ordering where it will not.

$\endgroup$
2
$\begingroup$

I'm not sure what you mean by a "formula that works for all graphs" – what would the variables of such a formula represent? Since it's NP-hard to determine the chromatic number of a graph (the minimum number of colours required), there's unlikely to be any simple way of doing it in general.

For the specific graph in the question, the easiest way is to find a colouring with some number of colours and then prove that no smaller number of colours can work. In this case, it's easy to find a 2-colouring of the graph and there's clearly no 1-colouring, since every vertex is adjacent to at least one other vertex.

For part b, are you familiar with greedy colouring algorithms? In particular, if the next vertex to be considered has no neighbours that have already been coloured, that vertex will receive colour $1$. So, one way to produce an ordering that makes the greedy algorithm use a suboptimal number of colours is to find two non-adjacent vertices $X$ and $Y$ that must always have different colours in an optimal colouring, and begin your ordering $X,Y, \dots\;$. Doing this requires understanding what optimal colourings look like, which is fairly simple for the given graph but, as I stated above, is hard in general.

$\endgroup$
  • $\begingroup$ Cheers, I see that $A, F, C, D, E, B$ will require three colors with the greedy algorithm. $\endgroup$ – sonicboom Aug 10 '14 at 17:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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