IsEdgeColorable - Maple Help

GraphTheory

 IsEdgeColorable
 test if graph is edge-colorable with k colors

 Calling Sequence IsEdgeColorable(G, k, col) IsEdgeColorable(G, k, d, col)

Parameters

 G - undirected graph k - non-negative integer (the number of colors) d - (optional) positive integer (distance) col - (optional) name

Description

 • The IsEdgeColorable(G,k) function returns true if the graph G is k-edge colorable and false otherwise.  That is, if the edges of G can be colored with k colors such that no two incident edges have the same color.
 • If an optional argument d is specified, then IsEdgeColorable(G,k,d) returns true if the graph G is (k,d)-edge colorable, and false otherwise. That is, it returns true if the edges of G can be colored with k colors such that two edges with any given color are at least distance d apart.  When d is not specified it is assumed to be 1.
 • If a name col is specified, then this name is assigned the list of colors of an optimal proper coloring of edges of G, if it exists. The algorithm uses a backtracking technique.
 • The problem of testing if a graph is k-colorable is NP-complete, 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{with}\left(\mathrm{SpecialGraphs}\right):$
 > $G≔\mathrm{PetersenGraph}\left(\right):$
 > $\mathrm{IsEdgeColorable}\left(G,3\right)$
 ${\mathrm{false}}$ (1)
 > $\mathrm{IsEdgeColorable}\left(G,4,'\mathrm{col}'\right)$
 ${\mathrm{true}}$ (2)
 > $\mathrm{col}$
 $\left[\left\{\left\{{1}{,}{6}\right\}{,}\left\{{2}{,}{3}\right\}{,}\left\{{4}{,}{5}\right\}{,}\left\{{7}{,}{8}\right\}{,}\left\{{9}{,}{10}\right\}\right\}{,}\left\{\left\{{1}{,}{5}\right\}{,}\left\{{3}{,}{4}\right\}{,}\left\{{6}{,}{10}\right\}{,}\left\{{8}{,}{9}\right\}\right\}{,}\left\{\left\{{2}{,}{9}\right\}{,}\left\{{3}{,}{7}\right\}{,}\left\{{4}{,}{10}\right\}{,}\left\{{5}{,}{8}\right\}\right\}{,}\left\{\left\{{1}{,}{2}\right\}{,}\left\{{6}{,}{7}\right\}\right\}\right]$ (3)
 > $\mathrm{map}\left(\mathrm{nops},\mathrm{col}\right)$
 $\left[{5}{,}{4}{,}{4}{,}{2}\right]$ (4)
 > $\mathrm{IsEdgeColorable}\left(G,11,3,'\mathrm{col}'\right)$
 ${\mathrm{true}}$ (5)
 > $\mathrm{col}$
 $\left[\left\{{1}{,}{2}\right\}{=}{0}{,}\left\{{1}{,}{5}\right\}{=}{3}{,}\left\{{1}{,}{6}\right\}{=}{6}{,}\left\{{2}{,}{3}\right\}{=}{3}{,}\left\{{2}{,}{9}\right\}{=}{8}{,}\left\{{3}{,}{4}\right\}{=}{6}{,}\left\{{3}{,}{7}\right\}{=}{9}{,}\left\{{4}{,}{5}\right\}{=}{10}{,}\left\{{4}{,}{10}\right\}{=}{2}{,}\left\{{5}{,}{8}\right\}{=}{7}{,}\left\{{6}{,}{7}\right\}{=}{1}{,}\left\{{6}{,}{10}\right\}{=}{9}{,}\left\{{7}{,}{8}\right\}{=}{4}{,}\left\{{8}{,}{9}\right\}{=}{0}{,}\left\{{9}{,}{10}\right\}{=}{5}\right]$ (6)
 > $\mathrm{IsEdgeColorable}\left(G,7,2\right)$
 ${\mathrm{false}}$ (7)