GraphTheory - Maple Programming Help

Online Help

All Products    Maple    MapleSim


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

GraphTheory

  

GreedyColor

 

Calling Sequence

Parameters

Description

Examples

Calling Sequence

GreedyColor(G, perm)

Parameters

G

-

undirected unweighted graph

perm

-

(optional) list of vertex labels

Description

• 

The GreedyColor command colors the vertices of the graph in the order given by perm, one at a time, assigning to each vertex the smallest available color. If the permutation perm is not specified, a heuristic is used, the permutation being given by the following rule: a vertex with lowest degree is removed from the graph, the heuristic permutation for the remaining graph is determined recursively, and the removed vertex is put at the end of this permutation. This yields a coloring with at most d+1 colors, where d is such that every subgraph of G contains a vertex of degree at most d. The parameter d is also known as the degeneracy of G.

• 

The output consists the number of colors used, followed a list that specifies the coloring of the vertices.

Examples

with(GraphTheory):

C6 := CycleGraph(6);

C6Graph 1: an undirected unweighted graph with 6 vertices and 6 edge(s)

(1)

GreedyColor(C6);

2,0,1,0,1,0,1

(2)

GreedyColor(C6, [1, 4, 2, 5, 3, 6]);

3,0,1,2,0,1,2

(3)

See Also

ChromaticNumber

GreedyClique

IsVertexColorable