IGraph/M now includes functions for computing vertex colourings efficiently.

To check if a graph g is k-vertex-colourable use,

IGKVertexColoring[g, k]

If the answer is yes, {coloring} will be returned. If it is no, {} will be returned.

To compute a minimum colouring, use IGMinimumVertexColroing. To just find the chromatic number, use IGChromaticNumber.

There are analogous IGKEdgeColoring and IGMinimumEdgeColoring functions.

If you want a fast but not necessarily minimal colouring, use IGVertexColoring and IGEdgeColoring.

Note that IGraph/M requires Mathematica 10.0 or later.

IGraph/M now includes functions for computing vertex colourings efficiently.

To check if a graph g is k-vertex-colourable use,

IGKVertexColoring[g, k]

If the answer is yes, {coloring} will be returned. If it is no, {} will be returned.

To compute a minimum colouring, use IGMinimumVertexColroing. To just find the chromatic number, use IGChromaticNumber.

There are analogous IGKEdgeColoring and IGMinimumEdgeColoring functions.

If you want a fast but not necessarily minimal colouring, use IGVertexColoring and IGEdgeColoring.

We can also visualize the colourings easily.

g = GraphData["DodecahedralGraph"];

Graph[g, GraphStyle -> "BasicBlack", VertexSize -> Large] // 
 IGVertexMap[ColorData[106], VertexStyle -> IGMinimumVertexColoring]

Graph[g, GraphStyle -> "BasicBlack", EdgeStyle -> Thickness[0.02]] // 
 IGEdgeMap[ColorData[106], EdgeStyle -> IGMinimumEdgeColoring]

Note that IGraph/M requires Mathematica 10.0 or later.