Brelaz's Heuristic Algorithm
An algorithm which can be used to find a good, but not necessarily minimal, edge or vertex coloring for a graph. However, the algorithm does minimally color complete k-partite graphs.
Brelaz's algorithm can be applied using BrelazColoring[g] in the Wolfram Language package Combinatorica` , and a guaranteed minimal vertex coloring can be found for small graphs using backtracking with MinimumVertexColoring[g].
Contact the MathWorld Team
bicolorable graph
