GraphTheory - Maple Programming Help

Home : Support : Online Help : Mathematics : Discrete Mathematics : Graph Theory : GraphTheory Package : GraphTheory/ChromaticNumber

GraphTheory

 ChromaticNumber

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

Parameters

 G - undirected unweighted graph col - (optional) name

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. Another optional name, if provided, is not assigned.

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