Every graph can be optimally colored greedily. I was at a conference today and someone said that if the graph $G$ has chromatic number $n$ then there is a way to order the vertices so that coloring greedily gives us a coloring with $n$ colors. By greedy coloring I mean you assume you have colors $1,2,3\dots$ and you label the vertices $1$ through $n$. And you color the vertices in increasing order. Using the smallest color you can each time. The speaker said this was not hard to prove, but I haven't been able to do so.

Start from a coloring, you label the vertices increasingly by color: the vertices colored by color 1 are the first vertices in the list, then the vertices colored by color 2 are next and so on.

Now, if you do a greedy coloring, you can prove that you get (a possibly new) coloring of this graph.

You can prove that this coloring has the desired property by proving the stronger statement: for each vertex $1 \leq j \leq k$ the new color is less or equal than the old color. This means you use at most $n$ colors.