GraphTheory - Maple Programming Help

Online Help

All Products    Maple    MapleSim


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

GraphTheory

  

IsVertexColorable

 

Calling Sequence

Parameters

Description

Examples

Calling Sequence

IsVertexColorable(G, k, col)

IsVertexColorable(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 IsVertexColorable(G,k) function returns true if the graph G is k-colorable and false otherwise.  That is, if the vertices of G can be colored with k colors such that no two adjacent vertices have the same color.

• 

If an optional argument d is specified, then IsVertexColorable(G,k,d) returns true if the graph G is (k,d) colorable, and false otherwise. That is, it returns true if the vertices of G can be colored with k colors such that two vertices 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 a coloring of the vertices of G, if it exists.

• 

The algorithm first tries a greedy coloring of the vertices of G starting with a maximum clique in G.  If this fails to find a k-coloring it does an exhaustive search using a backtracking algorithm.

• 

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:

PPetersenGraph

PGraph 1: an undirected unweighted graph with 10 vertices and 15 edge(s)

(1)

IsVertexColorableP,2

false

(2)

IsVertexColorableP,3,col

true

(3)

col

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

(4)

J7FlowerSnark7:

IsVertexColorableJ7,7,3,col

true

(5)

col

0,3,6,2,5,1,4,3,0,3,0,3,6,2,6,2,5,2,5,1,5,1,4,1,4,0,4,0

(6)

IsVertexColorableJ7,9,4

false

(7)

See Also

ChromaticNumber

CircularChromaticNumber

GreedyColor

IsEdgeColorable