compute chromatic number of a graph
ChromaticNumber(G, opt, col)
undirected unweighted graph
(optional) equation of the form method = value; specify method to use
(optional) identical name bound
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.
P ≔ PetersenGraph⁡:
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.
Download Help Document