9
$\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?

$\endgroup$
8
$\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$
5
$\begingroup$

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]

enter image description here

Compute its chromatic number and chromatic index:

IGChromaticNumber[g]
(* 3 *)

IGChromaticIndex[g]
(* 6 *)

Visualize a vertex colouring:

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

enter image description here

Visualize an edge colouring:

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

enter image description here

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]

enter image description here

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

| improve this answer | |
$\endgroup$
  • $\begingroup$ This should be much more efficient than the solution in my answer. $\endgroup$ – Juho Apr 8 at 4:40

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.