GraphTheory - Maple Programming Help

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

GraphTheory

 ChromaticIndex
 EdgeChromaticNumber

 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

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $\mathrm{K4}≔\mathrm{CompleteGraph}\left(4\right)$
 ${\mathrm{K4}}{≔}{\mathrm{Graph 1: an undirected unweighted graph with 4 vertices and 6 edge\left(s\right)}}$ (1)
 > $\mathrm{EdgeChromaticNumber}\left(\mathrm{K4},'\mathrm{col}'\right)$
 ${3}$ (2)
 > $\mathrm{col}$
 $\left[\left\{\left\{{1}{,}{3}\right\}{,}\left\{{2}{,}{4}\right\}\right\}{,}\left\{\left\{{1}{,}{4}\right\}{,}\left\{{2}{,}{3}\right\}\right\}{,}\left\{\left\{{1}{,}{2}\right\}{,}\left\{{3}{,}{4}\right\}\right\}\right]$ (3)
 > $\mathrm{DrawGraph}\left(\mathrm{K4}\right)$

Compatibility

 • The GraphTheory[ChromaticIndex] and GraphTheory[EdgeChromaticNumber] commands were updated in Maple 2019.
 • The method option was introduced in Maple 2019.