GraphTheory - Maple Programming Help

Online Help

All Products    Maple    MapleSim


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

GraphTheory

  

ChromaticNumber

  

compute the chromatic number of a graph

 

Calling Sequence

Parameters

Options

Description

Examples

Compatibility

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

withGraphTheory:

withSpecialGraphs:

PPetersenGraph:

ChromaticNumberP,bound

3..3

(1)

ChromaticNumberP,col

3

(2)

col

2,5,7,10,4,6,9,1,3,8

(3)

Compatibility

• 

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.

See Also

CircularChromaticNumber

EdgeChromaticNumber

GreedyColor

IsVertexColorable

Mycielski