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.

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

$\mathrm{IsEdgeColorable}\left(G\,4\,'\mathrm{col}'\right)$

$\mathrm{true}$

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

$\mathrm{map}\left(\mathrm{nops}\,\mathrm{col}\right)$

$\left[5\,4\,4\,2\right]$

$\mathrm{IsEdgeColorable}\left(G\,11\,3\,'\mathrm{col}'\right)$

$\mathrm{true}$

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

$\mathrm{IsEdgeColorable}\left(G\,7\,2\right)$

$\mathrm{false}$