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

Question

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?

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.

Answer 2

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.