ChromaticNumber - Maple Help

GraphTheory

 ChromaticNumber
 compute chromatic number of a graph

 Calling Sequence ChromaticNumber(G, opt, col) ChromaticNumber(G, 'bound')

Parameters

 G - undirected unweighted graph opt - (optional) equation of the form method = value; specify method to use col - (optional) name bound - (optional) identical name bound

Options

 • 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.

Description

 • 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.

Examples

 > $\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}$ (1)
 > $\mathrm{ChromaticNumber}\left(P,'\mathrm{col}'\right)$
 ${3}$ (2)
 > $\mathrm{col}$
 $\left[\left[{2}{,}{5}{,}{7}{,}{10}\right]{,}\left[{4}{,}{6}{,}{9}\right]{,}\left[{1}{,}{3}{,}{8}\right]\right]$ (3)

Compatibility

 • The GraphTheory[ChromaticNumber] command was updated in Maple 2018.
 • The method option was introduced in Maple 2018.