Sign up ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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?

share|improve this question
@DanielLichtblau It is relevant to point out the source claims to to use the Misra-Gries algorithm, so it is not always optimal. – Juho Mar 12 at 13:54

1 Answer 1

You can compute the chromatic index of a graph by first observing it is equivalent to the chromatic number of the line graph of the graph. This immediately suggests straightforward algorithms:

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

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

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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