IGraph/M now provides graph colouring functionality that is well integrated with the rest of Mathematica. You no longer need Combinatorica for this.
Demo:
Let's make a graph:
g = StarGraph[5, VertexSize -> Large];
Compute a minimum colouring and visualize it:
g // IGVertexMap[ColorData[112], VertexStyle -> IGMinimumVertexColoring]
Transform it into a larger graph that needs one more colour:
g2 = IGMycielskian[g, VertexSize -> Large]
Colour it:
g2 // IGVertexMap[ColorData[112], VertexStyle -> IGMinimumVertexColoring]
Obtain the colouring as a list:
IGMinimumVertexColoring[g2]
(* {1, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1} *)
Direct and explicit verification that the same graph is not 2-colourable:
IGKVertexColoring[g2, 2]
(* {} *)
Run a fast colouring algorithm that does not guarantee minimum colouring.
IGVertexColoring[g2]
(* {1, 2, 2, 2, 2, 3, 2, 2, 2, 2, 1} *)
It gave us a different result, also with 3 colours.
Directly compute the chromatic number:
IGChromaticNumber[g2]
(* 3 *)