Online Help

method=one of hybrid, optimal, brelaz, dsatur, greedy, welshpowell, or sat.

Specifies the algorithm to use in computing the chromatic number. The default, method=hybrid, uses a hybrid strategy which runs the optimal and sat methods in parallel and returns the result of whichever method finishes first. The optimal method computes a coloring of the graph with the fewest possible colors; the sat method does the same but does so by encoding the problem as a logical formula.

The remaining methods, brelaz, dsatur, greedy, and welshpowell are heuristics which are not guaranteed to return a minimal result, but which may be preferable for reasons of speed.

ChromaticNumber computes the chromatic number of a graph G.

If a name col is specified, then this name is assigned the list of color classes of an optimal proper coloring of vertices. The algorithm uses a backtracking technique.

If the option `bound` is provided, then an estimate of the chromatic number of the graph is returned. An optional name, col, if provided, is not assigned.

The task of verifying that the chromatic number of a graph is k is an NP-complete problem, meaning that no polynomial-time algorithm is known. The exhaustive search will take exponential time on some graphs.

$\mathrm{with}\left(\mathrm{GraphTheory}\right)\:$

$\mathrm{with}\left(\mathrm{SpecialGraphs}\right)\:$

$P≔\mathrm{PetersenGraph}\left(\right)\:$

$\mathrm{ChromaticNumber}\left(P\,'\mathrm{bound}'\right)$

$3..3$

$\mathrm{ChromaticNumber}\left(P\,'\mathrm{col}'\right)$

$3$

$\mathrm{col}$

$\left[\left[2\,5\,7\,10\right]\,\left[4\,6\,9\right]\,\left[1\,3\,8\right]\right]$

The GraphTheory[ChromaticNumber] command was updated in Maple 2018.

The method option was introduced in Maple 2018.

For more information on Maple 2018 changes, see Updates in Maple 2018 .