Coloring a graph using the new built-in commands

With very minimal adjustment of the original Combinatorica code, here is an implementation of Brelaz coloring:

brelaz[g_?GraphQ] := 
     Module[{m = 0, v = VertexCount[g], cd, color, p, nc, e},
       cd = color = ConstantArray[0, v];
       While[m >= 0,
             p = Position[cd, m][[1, 1]]; 
             e = AdjacencyList[g, p];
             nc = Append[color[[e]], 0];
             color[[p]] = Min[Complement[Range[Max[nc] + 1], nc]];
             cd[[p]] = -2 v; 
             Scan[(cd[[#]]++) &, e]; 
             m = Max[cd]
       ];
       color
     ]

Test:

col = brelaz[PetersenGraph[5, 2]]
   {1, 1, 2, 2, 3, 2, 3, 1, 3, 1}

PetersenGraph[5, 2, EdgeStyle -> Gray, 
              VertexStyle -> MapIndexed[First[#2] -> ColorData[61, #1] &, col], 
              VertexSize -> Small]

Compare with version 5.2:

<<DiscreteMath`Combinatorica`

VertexColoring[PetersenGraph, Algorithm -> Brelaz]
   {1, 1, 2, 2, 3, 2, 3, 1, 3, 1}

---

For completeness, here is the corresponding adapted edge coloring algorithm:

edgeColoring[g_?GraphQ] := Module[{c = brelaz[LineGraph[g]], e, se},
    e = Map[Sort, List @@@ EdgeList[g]];
    se = Sort[MapIndexed[Prepend[#2, #1] &, e]];
    Map[Last, Sort[Reverse[MapThread[Prepend, {se, c}], 2]]]]

IGraph/M 0.3.93 and later include the same colouring algorithm as Combinatorica.

Needs["IGraphM`"]

IGVertexMap[
 ColorData[97],
 VertexStyle -> IGVertexColoring,
 PetersenGraph[VertexSize -> Large, GraphStyle -> "BasicBlack"]
]

Note that while Combinatorica claims to implement Brélaz's heuristic, the algorithm is not the same described by Brélaz here. Combinatorica chooses vertices based on the number of already coloured neighbours. Brélaz suggests choosing based on the distinct neighbouring colours ("saturation degree").

In IGraph/M 0.3.98 and later you can also use IGMinimumVertexColoring to obtain an optimal colouring.