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 ].
See also Chromatic Number ,
Edge Coloring ,
Graph Coloring ,
Minimum
Vertex Coloring ,
Vertex Coloring
Explore 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. Referenced on Wolfram|Alpha Brelaz's Heuristic Algorithm
Cite this as:
Weisstein, Eric W. "Brelaz's Heuristic Algorithm."
From MathWorld https://mathworld.wolfram.com/BrelazsHeuristicAlgorithm.html
Subject classifications
