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.