8
$\begingroup$

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?

|improve this question
$\endgroup$
7
$\begingroup$

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.

|improve this answer
$\endgroup$

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.