# How to figure out the minimal number of colors needed to color specific given graphs?

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.

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.
• Cheers, I see that $A, F, C, D, E, B$ will require three colors with the greedy algorithm. – sonicboom Aug 10 '14 at 17:17