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 Heuristic Algorithm
See also
Chromatic Number, Edge Coloring, Graph Coloring, Minimum Vertex Coloring, Vertex ColoringExplore with Wolfram|Alpha
References
Brelaz, D. "New Methods to Color the Vertices of a Graph." Comm. ACM 22, 251-256, 1979.Skiena, S. "Finding a Vertex Coloring." §5.5.3 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 214-215, 1990.Referenced on Wolfram|Alpha
Brelaz's Heuristic AlgorithmCite this as:
Weisstein, Eric W. "Brelaz's Heuristic Algorithm." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/BrelazsHeuristicAlgorithm.html