GraphTheory - Maple Programming Help

Online Help

All Products    Maple    MapleSim


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

GraphTheory

  

IsEdgeColorable

 

Calling Sequence

Parameters

Description

Examples

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

withGraphTheory:

withSpecialGraphs:

GPetersenGraph:

IsEdgeColorableG,3

false

(1)

IsEdgeColorableG,4,col

true

(2)

col

1,6,2,3,4,5,7,8,9,10,1,5,3,4,6,10,8,9,2,9,3,7,4,10,5,8,1,2,6,7

(3)

mapnops,col

5,4,4,2

(4)

IsEdgeColorableG,11,3,col

true

(5)

col

1,2=0,1,5=3,1,6=6,2,3=3,2,9=8,3,4=6,3,7=9,4,5=10,4,10=2,5,8=7,6,7=1,6,10=9,7,8=4,8,9=0,9,10=5

(6)

IsEdgeColorableG,7,2

false

(7)

See Also

CircularChromaticIndex

EdgeChromaticNumber

IsVertexColorable