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
What kind of issue would you like to report? (Optional)