GraphTheory - Maple Programming Help

Online Help

All Products    Maple    MapleSim


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

GraphTheory

  

ChromaticIndex

  

EdgeChromaticNumber

 

Calling Sequence

Parameters

Options

Description

Examples

Compatibility

Calling Sequence

ChromaticIndex(G, opt, col)

EdgeChromaticNumber(G, opt, col)

Parameters

G

-

undirected unweighted graph

opt

-

(optional) equation of the form method = value; specify method to use

col

-

(optional) name

Options

• 

method=one of fastest, optimal, or sat.

  

Specifies the algorithm to use in computing the chromatic index. The default, method=fastest, 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 an edge 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.

Description

• 

ChromaticIndex and EdgeChromaticNumber compute the chromatic index (or edge 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 edge coloring.

• 

The algorithm uses a backtracking technique, except when G is bipartite, where a more efficient algorithm is used.

• 

The task of verifying that the chromatic index 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:

K4CompleteGraph4

K4Graph 1: an undirected unweighted graph with 4 vertices and 6 edge(s)

(1)

EdgeChromaticNumberK4,col

3

(2)

col

1,3,2,4,1,4,2,3,1,2,3,4

(3)

DrawGraphK4

Compatibility

• 

The GraphTheory[ChromaticIndex] and GraphTheory[EdgeChromaticNumber] commands were updated in Maple 2019.

• 

The method option was introduced in Maple 2019.

• 

For more information on Maple 2019 changes, see Updates in Maple 2019.

See Also

ChromaticNumber

CircularEdgeChromaticNumber

IsEdgeColorable