# 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?

• Commented Oct 30, 2012 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.
– Juho
Commented Mar 12, 2015 at 13:54

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.

IGraph/M has some graph colouring functionality.

Let us create a graph:

style = {VertexSize -> Large,
EdgeStyle -> Directive[AbsoluteThickness[5], Opacity[1]],
GraphStyle -> "BasicBlack"};

SeedRandom[998]
g = RandomGraph[{10, 20}, style]


Compute its chromatic number and chromatic index:

IGChromaticNumber[g]
(* 3 *)

IGChromaticIndex[g]
(* 6 *)


Visualize a vertex colouring:

g // IGVertexMap[ColorData[100], VertexStyle -> IGMinimumVertexColoring]


Visualize an edge colouring:

g // IGEdgeMap[ColorData[100], EdgeStyle -> IGMinimumEdgeColoring]


Visualize an edge colouring in a non-simple graph in Mathematica 12.1:

mg = Graph[UndirectedEdge @@@ RandomInteger[{1, 10}, {30, 2}], style];

mg // EdgeTaggedGraph // IGEdgeMap[ColorData[100], EdgeStyle -> IGMinimumEdgeColoring]


IGraph/M can compute a colouring for multigraphs in all supported Mathematica versions, but only Mathematica 12.1 can visualize them.

• This should be much more efficient than the solution in my answer.
– Juho
Commented Apr 8, 2020 at 4:40