How can I compute the chromatic index and number of a graph?

I saw a recent question from M.R. and realized there is no function to compute the chromatic index and number of a graph, other than a really slow method in the now deprecated Combinatorica.

So, how can I compute the chromatic index and number of a graph?

-
–  Daniel Lichtblau Oct 30 '12 at 21:44
@DanielLichtblau It is relevant to point out the source claims to to use the Misra-Gries algorithm, so it is not always optimal. –  mrm Mar 12 at 13:54

ChromaticNumber[g_] := MinValue[{z, z > 0 && ChromaticPolynomial[g, z] > 0}, z, Integers];

Notice we make use of ChromaticPolynomial which was incorporated into the main language in V10.