Online Help

method=one of hybrid, optimal, or sat.

Specifies the algorithm to use in computing the chromatic index. 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 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.

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.

$\mathrm{with}\left(\mathrm{GraphTheory}\right)\:$

$\mathrm{K4}≔\mathrm{CompleteGraph}\left(4\right)$

$\mathrm{K4}≔\mathrm{Graph\; 1:\; an\; undirected\; graph\; with\; 4\; vertices\; and\; 6\; edges}$

$\mathrm{EdgeChromaticNumber}\left(\mathrm{K4}\,'\mathrm{col}'\right)$

$3$

$\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]$

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 .