test if graph is edge-colorable with k colors
IsEdgeColorable(G, k, col)
IsEdgeColorable(G, k, d, col)
non-negative integer (the number of colors)
(optional) positive integer (distance)
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.
G ≔ PetersenGraph⁡:
Download Help Document